L144 Binary Tree Preorder Traversal

Problem

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

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,2,3]

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

Solution:

S1: Recursion

we need create the result our of the function so we could add the value;

pre order: root, left, right;

private List<Integer> result;
public List<Integer> preOrder(TreeNode root){
   result = new ArrayList<>():
   helper(root);
   return result;
}
private void helper(TreeNode root){
   if(root == null) return;
   result.add(root.val);
   helper(root.left);
   helper(root.right);
}

S2: Iteration

stack is used to store the previous root.val. Since it is preorder root -> left -> right, when we get the end of the most left node(node.left = null), we need to return to it's root, and get right.val

public List<Integer> preOrder(TreeNode root){
    List<Integer> res = new ArrayList<>();
    if(root == null) return res;
    Stack<TreeNode> stack = new Stack<>();
    while(root != null || !stack.isEmpty()){
        if(root != null){
            stack.push(root);
            res.add(root.val);
            root = root.left;
        }else{
            root = stack.pop();
            root = root.right;
        }
    }
    return res;
}