二叉樹中序周遊，先序周遊，後序周遊（遞歸棧，非遞歸棧，Morris Traversal）

例題

中序周遊94. Binary Tree Inorder Traversal
先序周遊144. Binary Tree Preorder Traversal
後序周遊145. Binary Tree Postorder Traversal
遞歸棧
遞歸函數棧的方法很基礎，寫法也很簡單，三種周遊方式之間隻需要改變一行代碼的位置即可
中序周遊

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    
    void inorder(TreeNode* root, vector<int>& v){
        if(root != nullptr) {
            inorder(root->left, v);
            v.push_back(root->val); // 改變位置的代碼
            inorder(root->right, v);
        }
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> v;
        
        inorder(root, v);
        return v;
    }
};

先序周遊

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    
    void inorder(TreeNode* root, vector<int>& v){
        if(root != nullptr) {
            v.push_back(root->val);
            inorder(root->left, v);
            inorder(root->right, v);
        }
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> v;
        
        inorder(root, v);
        return v;
    }
};

後序周遊

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    
    void inorder(TreeNode* root, vector<int>& v){
        if(root != nullptr) {
            inorder(root->left, v);
            inorder(root->right, v);
            v.push_back(root->val);
        }
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> v;
        
        inorder(root, v);
        return v;
    }
};

非遞歸棧

當樹的深度過大時，函數棧可能會溢出，這時候需要我們使用資料結構中的棧，來模拟節點在棧中的壓入和彈出

中序周遊

cur指針時刻指向需要處理的節點

如果目前節點不為空，則壓入棧中，并改變cur指針指向其左節點

如果目前節點為空，也代表空節點的中序周遊自動完成，無需壓棧，這時候需要彈出棧頂的節點，儲存棧頂節點的值，并更改cur指向其右子樹，以完成右子樹的中序周遊

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> v;
        stack<TreeNode*> s;
        TreeNode* cur = root;

        while(cur || !s.empty()){
            if(cur){
                s.push(cur);
                cur = cur->left;
            } else {
                cur = s.top();
                s.pop();
                v.push_back(cur->val);
                cur = cur->right;
            }
        }
        
        return v;
    }
};

先序周遊

先序周遊與中序周遊代碼相比隻改變了儲存節點的值的代碼的位置，當先通路根的時候就記錄節點，而不是等左子樹周遊完，彈出根節點的時候再記錄

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> v;
        stack<TreeNode*> s;
        TreeNode* cur = root;

        while(cur || !s.empty()){
            if(cur){
                v.push_back(cur->val);
                s.push(cur);
                cur = cur->left;
            } else {
                cur = s.top();
                s.pop();
                cur = cur->right;
            }
        }
        
        return v;
    }
};

後序周遊

因為後序周遊的壓棧順序是左-右-根，由于先周遊完左子樹，然後周遊完右子樹，然後才能處理目前節點，為了和之前的代碼的結構保持一緻，我們可以反向處理，也就是按根-右-左的順序壓棧，

結果反向輸出即可

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> v;
        stack<TreeNode*> s;
        TreeNode* cur = root;

        while(cur || !s.empty()){
            if(cur){
                v.push_back(cur->val);
                s.push(cur);
                cur = cur->right;
            } else {
                cur = s.top();
                s.pop();
                cur = cur->left;
            }
        }
        
        reverse(v.begin(), v.end()); // 反向輸出結果
        return v;
    }
};

Morris Traversal

線索二叉樹，O(n)時間，常數空間

Morris Traversal方法周遊二叉樹（非遞歸，不用棧，O(1)空間）

就是目前節點的中序周遊前驅節點，如果此前驅節點的右指針為空，則将此前驅節點的右指針指向目前節點

當尋找目前節點的中序周遊前驅節點時，發現能循環到自己，說明左子樹已經周遊完，需要周遊右子樹

中序周遊

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        TreeNode* cur, *prev;
        vector<int> v;
        cur = root;
        prev = nullptr;
        
        while(cur){
            if(cur->left == nullptr){
                v.push_back(cur->val);
                cur = cur->right;
            } else {
                prev = cur->left;
                while(prev->right != nullptr && prev->right != cur) 
                    prev = prev->right;
                
                if(prev->right == nullptr){
                    prev->right = cur;
                    cur = cur->left;
                } else {
                    v.push_back(cur->val);
                    prev->right = nullptr;
                    cur = cur->right;
                }
            }
        }
        
        return v;
    }
};

先序周遊

同樣先序周遊與中序周遊相比也隻需要改變一行代碼的位置

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        TreeNode* cur, *prev;
        vector<int> v;
        cur = root;
        prev = nullptr;
        
        while(cur){
            if(cur->left == nullptr){
                v.push_back(cur->val);
                cur = cur->right;
            } else {
                prev = cur->left;
                while(prev->right != nullptr && prev->right != cur) 
                    prev = prev->right;
                
                if(prev->right == nullptr){
                    v.push_back(cur->val);
                    prev->right = cur;
                    cur = cur->left;
                } else {
                    prev->right = nullptr;
                    cur = cur->right;
                }
            }
        }
        
        return v;
    }
};

後序周遊

後序周遊需要反向輸出cur->left到cur的中序前驅結點之間的路徑

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    void reverse_traverse_reverse(TreeNode* cur, vector<int>& v){
        TreeNode* prev = nullptr;

        while(cur){
            auto right = cur->right;
            cur->right = prev;
            prev = cur;
            cur = right;
        }


        cur = prev;
        prev = nullptr;

        while(cur){
            auto right = cur->right;
            cur->right = prev;
            v.push_back(cur->val);
            prev = cur;
            cur = right;
        }
    }
    vector<int> postorderTraversal(TreeNode* root) {
        TreeNode* cur, *prev;
        vector<int> v;
        cur = new TreeNode(-1);
        prev = nullptr;
        cur->left = root;
        while(cur){
            if(cur->left == nullptr){
                cur = cur->right;
            } else {
                prev = cur->left;
                while(prev->right != nullptr && prev->right != cur)
                    prev = prev->right;
                
                if(prev->right == nullptr){
                    prev->right = cur;
                    cur = cur->left;
                } else {
                    prev->right = nullptr;
                    reverse_traverse_reverse(cur->left, v);
                    cur = cur->right;
                }
            }
        }
        
        return v;
    }
};

總結

三種周遊方式中，後序周遊的處理比較麻煩，但是無論是使用遞歸棧，非遞歸棧還是Morris Traversal，代碼的結構都是一樣的，中序和前序甚至隻有一行代碼位置的差别

使用棧的版本中，最壞空間複雜度為O（n）鍊型，平均空間複雜度為O（lgn）

Morris Traversal空間複雜度為O(1)

轉載于:https://www.cnblogs.com/qbits/p/11163161.html

二叉樹中序周遊，先序周遊，後序周遊（遞歸棧，非遞歸棧，Morris Traversal）

例題

遞歸棧

中序周遊

先序周遊

後序周遊

非遞歸棧

中序周遊

先序周遊

後序周遊

Morris Traversal

中序周遊

先序周遊

後序周遊

總結

繼續閱讀

goalng nil interface淺析持續學習

模組化：數學模組化

開源軟體：NoSql資料庫 - 圖資料庫 Neo4j轉載自原文位址：http://www.cnblogs.com/loveis715/p/5277051.html

資料在網絡7層中的傳輸過程

當今世界十大經典算法

字元串功能實作

【算法提高班】貪婪政策

《貪婪的動态規劃》

分治法實作求解最大子數組

UVA 10154:Weights and Measures Weights and Measures

Linux Kernel Development　學習

動态規劃、最小費用流例題 — nyoj_712 探尋寶藏

計算機開路人阿蘭·圖靈

基礎算法之二分查找

poj3249

PAT 1089 Insert or Merge[難]