卖萌的弱渣

I am stupid, I am hungry.

Binary Tree Inorder Traversal

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

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

  • Iterative solution
(Binary-Tree-Inorder-Traversal.py) download
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

# 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]
        """
        ret = []
        if not root:
            return ret

        stack = []
        node = root
        while node:
            stack.append(node)
            node = node.left

        while stack:
            node = stack.pop()
            ret.append(node.val)
            # push the left subtree of right child
            node = node.right
            while node:
                stack.append(node)
                node = node.left
        return ret

if __name__ == "__main__":
    sol = Solution()
    node1 = TreeNode(1)
    node2 = TreeNode(2)
    node3 = TreeNode(3)
    node1.right = node2
    node2.left = node3
    print sol.inorderTraversal(node1)
  • 更简练的java solution: 不需要预处理左字树
(Binary-Tree-Inorder-Traversal.java) download
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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new LinkedList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode cur = root;
        while (cur!=null || !stack.empty()){
            // 把左子树插入
            while (cur != null){
                stack.add(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            ret.add(cur.val);
            cur = cur.right;
        }
        return ret;
    }
}