[LeetCode] 94. Binary Tree Inorder Traversal

Posted on | In

Problem

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

Example:

1
2
3
4
5
6
7
8
Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]

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

Explanation

  1. To do it iteratively, we can create a stack to hold the TreeNode, and a cur pointer pointing the root first. We can illustrate the process below:

    1
    2
    3
    4
    5
                       1
             2           3
         4       5     6    x
       x    7
          8   x

  2. We first push the current node to the stack, then current node to its left node, push again, update the current node, until current node is null. In other word, now the stack is [1, 2, 4]. Then we pop the stack and push pop node’s value to res, so stack is [1, 2], res = [4]. Then we check if the poped node has right child, if it has right child, then we update cur to the right child node and now cur node is not null, and we repeate the above process and push it to the stack then update current node to its left node, push again, update the current node, until current node is null. So at some point stack is [1, 2, 7, 8], res = [4]. Then stack is [1, 2, 7], res = [4, 8], stack is [1, 2], res = [4, 8, 7], stack is [1], res = [4, 8, 7, 2], stack is [1, 5], res = [4, 8, 7, 2], stack is [1], res = [4, 8, 7, 2, 5], stack is [3], res = [4, 8, 7, 2, 5, 1], stack is [6], res = [4, 8, 7, 2, 5, 1, 3], stack is [], res = [4, 8, 7, 2, 5, 1, 3, 6].

  3. We end if stack is empty.

Solution

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;

        TreeNode cur = root;
        Stack<TreeNode> st = new Stack<>();
        while (cur != null || !st.isEmpty()) {
            if (cur != null) {
                st.push(cur);
                cur = cur.left;
            } else {
                cur = st.pop();
                res.add(cur.val);
                cur = cur.right;
            }
        }

        return res;
    }
}


// class Solution {
//     void helper(TreeNode root, List<Integer> res) {
//         if (root == null) {
//             return;
//         }
//         helper(root.left, res);
//         res.add(root.val);
//         helper(root.right, res);
//     }
//     public List<Integer> inorderTraversal(TreeNode root) {
//         List<Integer> res = new ArrayList<>();
//         if (root == null) return res;
//         helper(root, res);
//         return res;
//     }
// }