1. Straightforward recursive. Create new List<Integer> instance in each recursive call. BAD.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    /**
     * 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 LinkedList<>();
            if (root == null) return res;
            res.add(root.val);
            res.addAll(preorderTraversal(root.left));
            res.addAll(preorderTraversal(root.right));
            return res;
        }
    }

  2. Recursive with Helper function. Only create 1 List<Integer> instance. Good. 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    class Solution {
        public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> res = new LinkedList<>();
            pre(root, res);
            return res;
        }
        public void pre(TreeNode root, List<Integer> res) {
            if (root == null) return;
            res.add(root.val);
            pre(root.left, res);
            pre(root.right, res);
        }
    }

Why no judge if node is null inside helper function? Because it is recursive; it’s judging whether node is null at the beginning inside each recursion.

  1. Iterative. GOOD.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
        public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> res = new LinkedList<>();
            if (root == null) return res;
            Stack<TreeNode> st = new Stack<>();
            st.push(root);
            while (!st.empty()) {
                TreeNode node = st.pop();
                res.add(node.val);
                // 因为是栈,后push进去的left节点先加入res
                if (node.right != null) st.push(node.right);
                if (node.left != null) st.push(node.left);
            }
            return res;
        }
    }

There is a judge if node is null control flow because it is iteration. Manually judging is needed.