Star

Leetcode 94.Binary Tree Inorder Traversal

Posted on | In |

Question

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

Explanation

方法1：递归。(参考：数据结构：二叉树) base case： root为null返回一个空list。 之后按中序遍历来遍历左边，中间和右边的节点。

方法2：循环。 用stack存起来，先遍历左边，然后对每一个节点进行中序遍历。弹出Stack的同时，把值存在list里。

Code

Recursive

1
2
3
4
5
6
7
8
9
public List<Integer> inorderTraversal(TreeNode root) {
    // Recursive:
    List<Integer> list = new ArrayList<>();
    if (root == null) return list;
    list = inorderTraversal(root.left);
    list.add(root.val);
    list.addAll(inorderTraversal(root.right));
    return list;
}

Iterative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public List<Integer> inorderTraversal(TreeNode root) {
    // Iterative:
    Stack<TreeNode> stack = new Stack<>();
    List<Integer> list = new ArrayList<>();
    TreeNode curt = root;
    while(curt != null || !stack.empty()) {
        while(curt != null) {
            stack.add(curt);
            curt = curt.left;
        }
        curt = stack.pop();
        list.add(curt.val);
        curt = curt.right;
    }
    return list;
}