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].

思路

题目要求我们中序遍历一棵树。依照题意，应当先访问左子树，之后访问根，最后访问右子树。

利用递归实现起来很容易，利用深度优先遍历(DFS)即可实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        if (root):
            self.DFS(root,res) 
        return res
        
    def DFS(self, root, res):
        if (root.left):
            self.DFS(root.left, res)
        res.append(root.val)
        if (root.right):
            self.DFS(root.right, res)

题目又提出了进一步的要求，需要我们使用迭代的方法来解决问题。

一般来说，深度优先的操作可以转换为栈的操作。我们发现不仅需要用栈，还需要利用一个能存访问过节点的数据结构才行，不然就会无限循环访问左子树，无法跳出。

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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        stack = []
        res = []
        visit = {}
        if (root):
            stack.append(root)
            while(len(stack)):
                # 在这里要注意加入visited选项，如果访问过该节点，就停止查找。
                while (stack[-1].left and not visit.has_key(stack[-1].left)):
                    stack.append(stack[-1].left)
                cur = stack.pop()
                res.append(cur.val)
                visit[cur] = 0
                if (cur.right):
                    stack.append(cur.right)    
        return res