1. Description

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

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

2. Example

Given binary tree [1,null,2,3],

return [1,2,3].

3. Code

[tabby title="Stack"]

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class LeetCode0144 {

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int v) {
            val = v;
        }
    }

    public List preorderTraversal(TreeNode root) {

        List result = new ArrayList();

        Stack stack = new Stack();

        TreeNode p = root;

        while (!stack.isEmpty() || p != null) {
            if (p != null) {
                result.add(p.val);
                stack.push(p);
                p = p.left;
            } else {
                p = stack.pop();
                p = p.right;
            }
        }
        return result;
    }
}

[tabby title="Stack"]

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class LeetCode0144 {

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int v) {
            val = v;
        }
    }

    public List preorderTraversal(TreeNode root) {

        List result = new ArrayList();

        Stack stack = new Stack();

        TreeNode p = root;

        while (!stack.isEmpty() || p != null) {
            while (p != null) {
                result.add(p.val);
                stack.push(p);
                p = p.left;
            }
            p = stack.pop();
            p = p.right;

        }
        return result;
    }
}

[tabby title="Recursive"]

import java.util.ArrayList;
import java.util.List;

public class LeetCode0144 {

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int v) {
            val = v;
        }
    }

    List result = new ArrayList();

    public List preorderTraversal(TreeNode root) {

        if (root == null) {
            return result;
        }

        result.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);

        return result;
    }
}

[tabbyending]