두 갈래 나무의 전순, 중순, 후순이 두루 흐르는 교체 실현

두 갈래 나무의 전순, 중순, 후순은 역귀로 실현하는 것이 비교적 간단하다.그러나 귀속을 이용하는 데는 도전이 있다.현재 몇 가지 흔히 볼 수 있는 실현 방식을 간단하게 소개한다.
두 갈래 트리 노드는 다음과 같이 정의됩니다.

struct ListNode {
     int val;
      ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
};

1. 앞의 순서를 두루 훑어보다

앞의 순서는 중, 좌, 우이다.두 가지 이상의 시나리오가 있습니다.

// ： ， 。
 vector preorderTraversal(TreeNode *root) {
     vector res;
     if(!root)
         return res;
     stack st;
     st.push(root);
     while(!st.empty()){
         TreeNode* p = st.top();
         res.push_back(p->val);
         st.pop();
         if(p->right) st.push(p->right);
         if(p->left) st.push(p->left);
     }
     return res;
 }

// ： ， 。 ， ， 。
 vector preorderTraversal(TreeNode *root) {
     vector res;
     if(!root)
         return res;
     stack st;
     st.push(root);
     while(!st.empty()){
         TreeNode* p = st.top();
         res.push_back(p->val);
         st.pop();
         while(p->left){
             res.push_back(p->left->val);
             if(p->right) st.push(p->right);
             p = p->left;
         }
         if(p->right) st.push(p->right);
     }
     return res;
 }

2. 중서 두루 훑어보다

중간 순서가 반복되는 순서는 왼쪽, 중간, 오른쪽입니다.그 고전적인 사고방식은 현재 노드에 왼쪽 노드가 있을 때 현재 노드를 창고에 보관하고 왼쪽 노드를 현재 처리한다.현재 노드에 왼쪽 하위 노드가 없으면 왼쪽 트리가 모두 완성되었음을 나타냅니다. 현재 노드에 접근하고 오른쪽 하위 노드를 현재 노드로 설정합니다.

 vector inorderTraversal(TreeNode *root) {
     vector res;
     if(!root)
         return res;
     stack st;
     TreeNode* p = root;
     while(p || !st.empty()){
         if(p){
             st.push(p);
             p = p->left;
         }
         else{
             p = st.top();
             res.push_back(p->val);
             st.pop();
             p = p->right;
         }
     }
     return res;
 }

3. 후속 반복

뒤의 순서는 왼쪽, 오른쪽, 중입니다.다음은 두 가지 시나리오입니다.

// ： ： ， 。
// 。

 vector postorderTraversal(TreeNode *root){
     vector res;
     if(!root)  
         return res;
     stack st;
     TreeNode * pre = nullptr;
     st.push(root);
     while(!st.empty()){
         TreeNode * p = st.top();
         if( (!p->left && !p->right) ||
             (pre && (pre == p->left || pre == p->right)) ){
             res.push_back(p->val);
             st.pop();
             pre = p;
         }
         else{
             if(p->right) st.push(p->right);
             if(p->left) st.push(p->left);
         }
     }
     return res;        
 }

// ： ： ， 。
// ： ， ， 。 reverse ， ： ， ， 。

 vector postorderTraversal(TreeNode *root){
     vector res;
     if(!root)  
         return res;
     stack st;
     st.push(root);
     while(!st.empty()){
         TreeNode * p = st.top();
         res.push_back(p->val);
         st.pop();
         if(p->left) st.push(p->left);
         if(p->right) st.push(p->right);
     }
     reverse(res.begin(), res.end());
     return res;        
 }