94. Binary Tree Inorder Traversal.md

94. Binary Tree Inorder Traversal

思路

中序遍历二叉树。属于数据结构基本题。

思路一、递归

二叉树的中序、前序、后序遍历最方便的当然就是使用递归了。中序遍历某个节点时，先不访问它，先递归遍历其左子树，然后才访问该节点，最后递归遍历其右节点。

思路二、非递归

我们先定义一个栈，然后从根节点开始，进入循环，若当前节点不空那么将其入栈（暂不访问），然后向左下降进入下一循环；若为空则说明往左下降不动了，应该将栈顶元素取出 并访问，然后向右下降；循环直到栈空且当前节点也为空为止。

C++

思路一

class Solution {
private:
    void helper(TreeNode* root, vector<int> &res){
        if(!root) return;
        helper(root -> left, res);
        res.push_back(root -> val);
        helper(root -> right, res);
        
    }
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int>res;
        helper(root, res);
        return res;
    }
};

思路二

写法一

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int>res;
        stack<TreeNode *>stk;
        TreeNode* p = root;        
        while(!stk.empty() || p){
            if(p){ // 左: 一路向左下降
                stk.push(p);
                p = p -> left; 
            }
            else{
                p = stk.top(); // 中: 下降不动了, 访问栈顶元素
                stk.pop();
                res.push_back(p -> val);
                p = p -> right; // 右: 访问右子树
            }
        }
        return res;
    }
};

写法二

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int>res;
        stack<TreeNode*>stk;
        TreeNode *p = root;
        
        while(!stk.empty() || p){
            // 左: 一路向左下降
            while(p){ 
                stk.push(p);
                p = p -> left; 
            }
            // 中: 下降不动了, 访问栈顶元素
            p = stk.top(); stk.pop();
            res.push_back(p -> val);
            // 右: 访问右子树
            p = p -> right; 
        }
        
        return res;
    }
};