Binary Tree Traversal

Inorder Traversal: http://lintcode.com/submission/9193677/

public ArrayList<Integer> inorderTraversal(TreeNode root) {
    // write your code here
    ArrayList<Integer> res = new ArrayList<>();
    if(root == null){
        return res;
    }

    Deque<TreeNode> stack = new LinkedList<>();
    // stack.push(root);
    TreeNode curr = root;
    while(curr != null || !stack.isEmpty()){
        while(curr != null){
            stack.push(curr);
            curr = curr.left;
        }

        curr = stack.pop();
        res.add(curr.val);
        curr = curr.right;

    }
    return res;
}

public ArrayList<Integer> inorderTraversal(TreeNode root) {
    // write your code here
    ArrayList<Integer> res = new ArrayList<>();
    if(root == null){
        return res;
    }

    if(root.left != null) res.addAll(inorderTraversal(root.left));
    res.add(root.val);
    if(root.right != null) res.addAll(inorderTraversal(root.right));
    return res;
}

Preorder Traversal: http://lintcode.com/en/problem/binary-tree-preorder-traversal/

public ArrayList<Integer> preorderTraversal(TreeNode root) {
    // write your code here
    ArrayList<Integer> res = new ArrayList<>();
    if(root == null){
        return res;
    }

    Deque<TreeNode> stack = new LinkedList<>();
    stack.push(root);
    while(!stack.isEmpty()){
        root = stack.pop();
        res.add(root.val);
        if(root.right != null){
            stack.push(root.right);
        }

        if(root.left != null){
            stack.push(root.left);
        }
    }

    return res;
}

public ArrayList<Integer> preorderTraversal(TreeNode root) {
    // write your code here
    ArrayList<Integer> res = new ArrayList<>();
    if(root == null){
        return res;
    }

    res.add(root.val);
    res.addAll(preorderTraversal(root.left));
    res.addAll(preorderTraversal(root.right));

    return res;
}