[LeetCode] Problem 144 - Binary Tree Preorder Traversal

Posted on | In ,

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

Example

Input: [1,null,2,3]

1
2
3
4
5
1
 \
  2
 /
3

Output: [1,2,3]

Follow up

Recursive solution is trivial, could you do it iteratively?

Code

1
2
3
4
5
6
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    
    if (root == null)
        return result;

    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);

        if (node.right != null)
            stack.push(node.right);

        if (node.left != null)
            stack.push(node.left);
    }

    return result;
}