二叉树的遍历

中序遍历（三种方法）

94. Binary Tree Inorder 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;
    }
};

非递归栈

这个解法的关键是改变当前节点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;
        
        cur = root;
        while(cur || !s.empty()){
            if(cur){
                s.push(cur);
                cur = cur->left;
            } else {
                cur = s.top();
                v.push_back(cur->val);
                s.pop();
                cur = cur->right;
            }
        }
        
        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) {
        stack<TreeNode*> s;
        vector<int> v;
        
        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;
    }
};

后序遍历

非递归栈

二叉树的遍历

原文：https://www.cnblogs.com/qbits/p/11163161.html