Merge Two Binary Trees

recursive, 注意如果要建新node，deepCopy, 则总要建新node if(t1==null) return deepCopy(p2);

public class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if(t1==null&&t2==null) return null;
        else if(t1==null) return deepCopy(t2);
        else if(t2==null) return deepCopy(t1);
        else{
            TreeNode cur = new TreeNode(t1.val+t2.val);
            cur.left = mergeTrees(t1.left, t2.left);
            cur.right = mergeTrees(t1.right, t2.right);
            return cur;
        }
    }

    public TreeNode deepCopy(TreeNode t2){
        if(t2==null) return null;
        TreeNode root = new TreeNode(t2.val);
        root.left = deepCopy(t2.left);
        root.right = deepCopy(t2.right);
        return t2;
    }
}

in place, iterative 开始想怎么压入当前node后还能知道这个是左node还是right node。后来才反应过来直接压left和right就知道了。这个还要利用原先t1的结构。

   public TreeNode mergeTrees(TreeNode t1, TreeNode t2){
        if(t1==null) return t2;
        if(t2==null) return t1;
        Stack<TreeNode> s1 = new Stack<TreeNode>(); s1.push(t1);
        Stack<TreeNode> s2 = new Stack<TreeNode>(); s2.push(t2);
        TreeNode ans = t1;
        while(!s1.isEmpty()||!s2.isEmpty()){
            TreeNode cur1 = s1.pop();
            TreeNode cur2 = s2.pop();
            cur1.val +=cur2.val;
            if(cur1.right==null&&cur2.right!=null){
                cur1.right = cur2.right;
            }
            else if(cur1.right!=null && cur2.right!=null){
                s1.push(cur1.right);
                s2.push(cur2.right);
            }
            if(cur1.left==null&&cur2.left!=null){
                cur1.left = cur2.left;
            }
            else if(cur1.left!=null && cur2.left!=null){
                s1.push(cur1.left);
                s2.push(cur2.left);
            }
        }
        return ans;
    }