94. 二叉树的中序遍历

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

Solution1（递归版）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        inorder(root,res);
        return res;
    }
    
    void inorder(TreeNode* node, vector<int> &res){
        if(!node) return;
        inorder(node->left, res);
        res.push_back(node->val);
        inorder(node->right, res);
    }
};

Solution2（迭代版）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> ss;
        TreeNode* cur = root;
        while(cur || !ss.empty()){
            //优先把左节点push进栈。
            if(cur){
                ss.push(cur);
                cur = cur->left;
            }
            //该节点没有左节点，此时就该存储起来了。然后继续对右节点的操作。（自底向上的访问右节点）
            else{
                cur = ss.top();
                ss.pop();
                res.push_back(cur->val);
                cur = cur->right;
            }
        }
        return res;
    }
};

中序遍历的特点就是优先遍历左节点，之后是当前节点，最后是右节点。

所以遇到一个节点。先存储在栈内。考虑以下两点：

  • 有左节点，继续加入栈。
  • 没有左节点，处理该节点，并将该节点从栈中弹出，继续考虑该节点的右节点。

这里我在思考的时候，逻辑没有问题，在coding的时候，关注的是父节点与子节点的关系，这样写出来的代码很容易导致死循环（在左子节点判断玩后，无法弹出栈，下一层循环又继续进行左子节点的判断了）。看到评论是将每一个节点提出来作为观察对象。更加直接。