Binary Tree Preorder Traversal

lc 144

//divide & conquer
public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        if ( root == null) return list;
        list.add(root.val);
        List<Integer> left = preorderTraversal(root.left);
        List<Integer> right = preorderTraversal(root.right);   

        list.addAll(left);
        list.addAll(right);
        return list;
    }
}

stack

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        if ( root == null) return list;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.add(root);
        while ( ! stack.isEmpty()){
            TreeNode cur = stack.pop();
            list.add(cur.val);
            if ( cur.right != null)
                 stack.add (cur.right);
            if ( cur.left != null)
                stack.add (cur.left);
        } 
        return list;

   }

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        tranverse(root, result);
        return result;
    }

    //把root 为根的preorder 加到result里面
    private void tranverse(TreeNode root, List<Integer> result) {
        if(root == null) return;
        result.add(root.val);
        tranverse(root.left, result);
        tranverse(root.right,result);
    }