leetcode_binary_tree_inorder_traversal

发表于

难度：Meidum

中序遍历是：左 根 右。从根开始，把元素push进stack。从stack中取出top元素，然后查看左节点是否为空，如果不为空，则push进stack，一直做下去，直到左节点为空。当左节点为空时，将top元素pop除去，查看该元素右节点是否为空，如果不为空，则push进stack。在元素进栈时，要将元素记录下来，防止从右节点回来时，重复访问。

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
30
31
32
33
34
35
36
37
38
39
40
/**
 * 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) {
        if (root == NULL)   return {};
        stack<TreeNode*> s;
        unordered_map<TreeNode*,bool> m;
        s.push(root);
        m[root] = true;
        vector<int> ret;
        while(!s.empty())
        {
            TreeNode *cur = s.top();
            if(cur->left != NULL && m[cur->left] == false)
            {
                s.push(cur->left);
                m[cur->left] = true;
            }
            else
            {
                ret.push_back(cur->val);
                s.pop();
                if(cur->right != NULL)
                {
                    s.push(cur->right);
                    m[cur->right] = true;
                }
            }
        }
        return ret;
    }
};