Binary Tree Preorder Traversal leetcode

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

Example

Note

Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,2,3].
preorder 左 －－中－－ 右

第一种方法：迭代iteratively算法的时间复杂度是O(n), 而空间复杂度则是递归栈的大小，即O(logn)

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        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;
    }
}

第二种方法： 递归（Recursive）算法的时间复杂度是O(n), 而空间复杂度则是递归栈的大小，即O(logn)

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        traverse(root, result);
        return result;
        
    }
    private void traverse(TreeNode root, ArrayList<Integer> result){
        if (root == null){
            return;
        }
        result.add(root.val);
        traverse(root.left, result);
        traverse(root.right, result);
    }
}

第三种 分治(Divide & Conquer)

Generally, D&C questions would do 2 things at same time:

1. Divide – For binary tree, it mean solve left child, and solve right child
2. Conquer – return result value

public class Solution {
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if (root == null){
            return result;
        }
        //divide
        ArrayList<Integer> left = preorderTraversal(root.left);
        ArrayList<Integer> right = preorderTraversal(root.right);
        // Conquer
        result.add(root.val);
        result.addAll(left);//用addall方法是因为left类型是arraylist不是int
        result.addAll(right);
        return result;
        
    }
}