leetcode 617. 合并二叉树

解法：
递归：简单

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1==null) return root2;
        if(root2==null) return root1;
        return new TreeNode(root1.val+root2.val,mergeTrees(root1.left,root2.left),
        mergeTrees(root1.right,root2.right));
    }
}

迭代：
BFS：用三个队列

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1==null) return root2;
        if(root2==null) return root1;
        Queue queue=new LinkedList<>();
        Queue queue1=new LinkedList<>();
        Queue queue2=new LinkedList<>();
        TreeNode root=new TreeNode(root1.val+root2.val);
        queue.offer(root);
        queue1.offer(root1);
        queue2.offer(root2);
        while(!queue1.isEmpty()){
            TreeNode node=queue.poll(),node1=queue1.poll(),node2=queue2.poll();
            TreeNode l1=node1.left,r1=node1.right,l2=node2.left,r2=node2.right;
            if(l1!=null||l2!=null){
                if(l1!=null&&l2!=null){
                    TreeNode left=new TreeNode(l1.val+l2.val);
                    node.left=left;
                    queue.offer(left);
                    queue1.offer(l1);
                    queue2.offer(l2);
                }else if(l1==null){
                    node.left=l2;
                }else{
                    node.left=l1;
                }
            }
            if(r1!=null||r2!=null){
                if(r1!=null&&r2!=null){
                    TreeNode right=new TreeNode(r1.val+r2.val);
                    node.right=right;
                    queue.offer(right);
                    queue1.offer(r1);
                    queue2.offer(r2);
                }else if(r1==null){
                    node.right=r2;
                }else{
                    node.right=r1;
                }
            }
        }
        return root;
    }
}