[LeetCode] 144. Binary Tree Preorder Traversal

Posted on | In

Problem

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

Example:

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

Output: [1,2,3]

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

Explanation 1

  1. Preorder traversal is from root->left->right.

  2. Think of a tree that only has root node, left child, and right child first. We push the root child to the result array, then push the left children, then the right children. For the left children, we can then think of it as a root node recursivly run the helper function to push the so called root node to the array.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    void helper(TreeNode root, List<Integer> res) {
        if (root == null) return;
        res.add(root.val);
        helper(root.left, res);
        helper(root.right, res);
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }
}

Explanation 2

  1. To use an iterativly method, we can create a stack and a pointer to the root node. This method is also applies to Binary Tree Inorder Traversal and Binary Tree Postorder Traversal.

  2. Always start with while stack is not empty or p is not empty, because preorder traversal is root first, if the pointer node is not null, we can push the pointer node, which is the root node to the stack, and adding pointer node’s value to the result array. Then make the pointer points at the left child node, and repeat the while loop.

  3. For example in the below tree, pointer is initiallized point at 1, enter the while loop, we push it to stack and 1 to array; then pointer points at 2, then push to stack, add 2 to result array; then pointer points at 2’s left child which is null, if pointer is null, then we move the pointer to pop stack’s right child which means pop stack node is 2, its right child is 3, then we push 3 to stack and add 3 to result array; now pointer is at 3’s left child which is null, we pop 3, pointer at 3’s right child which still null, we pop stack which getting 1, make pointer points at 1’s right child which is null. We break out the while loop since stack is empty and pointer is null and we finish.

1
2
3
4
5
                1
              /
            2
              \
               3

Solution 2

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
/**
 * 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> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;

        TreeNode p = root;
        Stack<TreeNode> st = new Stack<>();

        while (p != null || !st.isEmpty()) {
            if (p != null) {
                st.push(p);
                res.add(p.val);
                p = p.left;
            } else {
                TreeNode popRootNode = st.pop();
                p = popRootNode.right;
            }
        }

        return res;
    }
}