前序中序後序周遊遞歸非遞歸實作

前序周遊

根-左兒子-右兒子

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
void preorder(TreeNode *root, vector<int> &v) {
    if (root == NULL) return;
    v.push_back(root->val);
    preorder(root->left,v);
    preorder(root->right,v);
}
           

非遞歸周遊時就是模拟棧，注意入棧順序即可

void preorder(TreeNode *root, vector<int> &v) {
    if (root == NULL) return;
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
       TreeNode *p = s.top();
       s.pop();
       if (p == NULL) continue;
       v.push_back(p->val);
       s.push(p->right);
       s.push(p->left);
    }
}
           

中序周遊

左二子-根-右兒子

void inorder(TreeNode *root, vector<int> &v) {
    if (root == NULL) return;
    inorder(root->left, v);
    v.push_back(root->val);
    inorder(root->right,v);
}
           

非遞歸周遊時要保證通路根節點前已經通路完左二子

void inorder(TreeNode *root, vector<int> &v) {
    if (root == NULL) return;
    stack<TreeNode*> s;
    TreeNode* p = root;
    while (p || !s.empty()) {
        while (p) {
            s.push(p);
            p = p->left;
        }
        if (!s.empty()) {
            p = s.top();
            v.push_back(p->val);
            s.pop();
            p = p->right; //這裡利用right為空或者非空來避開p重複進while
        }
    }
}
           

後序周遊

左兒子-右兒子-根

void postorder(TreeNode *root, vector<int> &v) {
    if (root == NULL) return;
    postorder(root->left, v);
    postorder(root->right, v);
    v.push_back(root->val);
}
           

後序周遊要保證兒子們都周遊完了才通路根。用一個輔助節點pre記錄上次通路的節點，則輸出該節點時隻有該節點為葉子節點或者pre為其兒子。否則把其兒子加入棧

void postorder(TreeNode *root, vector<int> &v) {
    if (root == NULL) return;
    stack<TreeNode*> s;
    TreeNode* cur = root;
    TreeNode* pre = NULL;
    s.push(root);
    while (!s.empty()) {
        cur = s.top();
        if ((cur->left == NULL && cur->right == NULL)||((pre)&&(pre == cur->left || pre == cur->right))){
            v.push_back(cur->val);
            pre = cur;
            s.pop();
        }
        else {                              //入棧和通路節點是不同循環的。因為已經通路了該節點說明其兒子節點已經被通路過了，不能再入棧
            if(cur->right) s.push(cur->right);
            if(cur->left) s.push(cur->left);
        }
    }
}