0144.md

144. Binary Tree Preorder Traversal

Level:

Topic:

Similar Problem:

• 94. Binary Tree Inorder Traversal
• 145. Binary Tree Postorder Traversal

Question

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

Input: root = [1,null,2,3]
Output: [1,2,3]

Intuition

Recursive:

• Node -> Left -> Right

Iterative:

DFS preorder

Stack

1. add the root val to list
2. push right node first
3. push left node

Code

Time: O(n)
Space: O(n)

Iterative

public List<Integer> preorderTraversal(TreeNode root) {
    if (root == null)
        return new ArrayList<>();

    List<Integer> ans = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    stack.add(root);

    while (!stack.isEmpty()) {
        root = stack.pop();
        ans.add(root.val);
        if (root.right != null)
            stack.push(root.right);
        if (root.left != null)
            stack.push(root.left);
    }
    return ans;
}

Recursive

List<Integer> ans = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
    preorder(root);
    return ans;
}


private void preorder(TreeNode root) {
    if (root == null)
        return;
    ans.add(root.val);
    preorder(root.left);
    preorder(root.right);
}