94. 二叉树的中序遍历

难度中等614

给定一个二叉树，返回它的中序 遍历。

示例:

1
2
3
4
5
6
7
8
输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

通过次数210,162

提交次数290,172

递归版本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 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 sol(TreeNode *root,vector<int>&nums){
        if(root==NULL){
            return;
        }
        sol(root->left,nums);
        nums.push_back(root->val);
        sol(root->right,nums);
        return ;
        ;
    }

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int>nums;
        sol(root,nums);
        return nums;

    }
};

迭代版本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
vector<int> inorderTraversal(TreeNode* root) {


    //迭代版本如下:
    stack<TreeNode*>S;
    vector<int>result;

    TreeNode*cur=root;
    
    while(cur!=NULL||!S.empty()){
        while(cur!=NULL){
            S.push(cur);
            cur=cur->left;
        }
        cur=S.top();
        result.push_back(cur->val);
        S.pop();
        cur=cur->right;
        /*

        # 这里设置 curr = curr.right， 如果 curr.right 不为空，那么说明 curr.right 是一棵树的根节点，走 while curr is not None 的逻辑。
        # 如果 curr.right 为空，那么这个右节点是空啊，没有意义，直接在 stack 中 pop 出一个节点。
        # 实际上，这里将一颗二叉树，看做了只有 根节点 和 左节点的树。

        */
        
    }
    return result;
}
image-20200809090152414
image-20200809090152414

以此图为例,算法首先从1开始,不停压栈,直到4,栈里面是 1 2 4,4在栈顶;然后cur=4,栈里面弹出4;然后cur=4->right,是空的,因此会跳过 while(cur!=NULL)这个循环,然后cur=2,栈里面弹出2,然后cur=2->right=5,因为5不是空的,开始压栈,直到7,此时栈里面是1,5,7……