Description

Given a binary tree, return the inorder traversal of its nodes’ values.

For example:
Given binary tree [1,null,2,3],

1
2
3
4
5
1
 \
  2
 /
3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

 

Solution

非递归实现思路：通过栈和一个外层while()循环模拟递归，过程始终维护一个指向当前节点的指针p，并在while()循环中根据条件：

1.该节点是否具有左右子树

2.该节点是否已被访问

3.该节点的值是否已记录

来确定该节点应归属于什么状态。状态也可以分为3类：

状态1：p有未遍历的左子树

状态2：p没有未遍历的左子树并且p有未遍历的右子树

状态3：p是叶子节点，或由于p的子树已遍历导致p既没有未遍历的左子树也没有未遍历的右子树

对于已经确定了p当前指向的节点所处的状态，分别作出相应的处理：

对状态1的处理：遍历p的左子树

对状态2的处理：判断节点的值是否已经加入结果：

​ <1>若未加入则加入结果，并继续遍历p的右子树

​ <2>若已加入结果，说该节点曾经到达过<1>状态，即当前p的位置是遍历完p的右子树后退回得到，因此，应当使p指向当前节点的父节点（利用出栈操作实现）

对状态3的处理：使p指向当前节点的父节点（利用出栈操作实现）

 

Code

迭代实现：

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
class Solution {
public:
    bool check(TreeNode* p,set<TreeNode*>& st)
    {
        set<TreeNode*>::iterator sit;
        sit = st.find(p);
        return sit != st.end() ? true : false;
    }
    
    vector<int> inorderTraversal(TreeNode* root)
    {
        vector<int> ret;
        if(root == NULL) return ret;
        set<TreeNode*> vised;
        set<TreeNode*> added;
        stack<TreeNode*> stk;
        TreeNode* p = root;
    
        //用stack模拟递归，每次循环将p确定在一个状态，执行一步动作，并重新开始循环
        while(true)
        {
            //p第一次到达某节点，将该节点记为已遍历
            if(!check(p, vised))
            {
                stk.push(p);
                printf("push %d\n",p->val);
                vised.insert(p);
            }
    
            //用相应信息判断p所处的状态
            if(p->left && !check(p->left, vised))
            {
                //状态1: p有未遍历的左子树
                p = p->left;
                continue;
            }
            else
            {
                //状态2 or 状态3: (p没有左子树) 或 (p没有未遍历的左子树)
    
                //检查p的值是否已经存入遍历结果
                if(!check(p, added))
                {
                    //p的值未存入结果，说明p的右子树还没遍历，随即进入p的右子树进行遍历
                    ret.push_back(p->val);
                    printf("add %d\n",p->val);
                    added.insert(p);
                }
                else
                {
                    //状态3: 由于p的子树已遍历，p既没有未遍历的左子树也没有未遍历的右子树
                    printf("pop %d\n",stk.top()->val);
                    stk.pop();
    
                    if(!stk.empty()) p = stk.top();//确保栈不空，再取元素
                    else break;
    
                    continue;
                }
    
                //判断p的状态2还是状态3
                if(p->right && !check(p->right, vised))
                {
                    //状态2: (p没有未遍历的左子树) and (p有未遍历的右子树)
                    p = p->right;
                }
                else
                {
                //状态3: (p是叶子节点) or
                //       (由于p的子树已遍历，p既没有未遍历的左子树也没有未遍历的右子树)
                    printf("pop %d\n",stk.top()->val);
                    stk.pop();
    
                    if(!stk.empty()) p = stk.top();
                    else break;
                }
            }
            if(stk.empty()) break;
        }
        return ret;
    }
};

递归实现：
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
class Solution {
public:
    void dfs(TreeNode* p, vector<int>& vec)
    {
        if(p->left)
        {
            //状态1: p有未遍历的左子树
            dfs(p->left, vec);
        }
        vec.push_back(p->val);
        if(p->right)
        {
            //状态2: (p没有未遍历的左子树) and (p有未遍历的右子树)
            dfs(p->right, vec);
        }
        else
        {
            //状态3: (p是叶子节点) or 
            //      (由于p的子树已遍历，p既没有未遍历的左子树也没有未遍历的右子树)
        }
    }
    
    vector<int> inorderTraversal(TreeNode* root)
    {
        vector<int> ret;
        if(root == NULL) return ret;
        dfs(root, ret);
        return ret;
    }
};