合并二叉树

leetCode–617（合并二叉树）

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

示例1：

输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]

示例 2：

输入：root1 = [1], root2 = [1,2]
输出：[2,2]

解法一：递归

先判断两个树是否为空，如果不为空将，两棵树的根节点相加，再递归遍历两个数的左子树和右子树。

代码为：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //递归
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1==null && root2==null) return null;
        if (root1==null || root2==null) return root1==null?root2:root1;
        root1.val = root1.val+root2.val;
        //合并该节点的左子树
        root1.left = mergeTrees(root1.left,root2.left);
        root1.right = mergeTrees(root1.right,root2.right);
        return root1;
    }
}

解法二：迭代

使用一个队列，只要两个树的左节点不为空，就将节点放入队列中，同理右子树也一样，只要右子树节点不为空，就将右子树加入到队列中，。

同时再定义一个合并后的队列，存放合并后的树。

代码为：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        //迭代
        if (root1==null) return root2;
        if (root2==null) return root1;
        Deque<TreeNode> merDeque = new ArrayDeque<>();//合并后的节点
        Deque<TreeNode> deque = new ArrayDeque<>();  //两个树中的节点
        TreeNode mer= new TreeNode(root1.val+root2.val);
        merDeque.addLast(mer);
        deque.addLast(root1);
        deque.addLast(root2);
        while (!merDeque.isEmpty() && !deque.isEmpty()){
            TreeNode node = merDeque.pop();
            TreeNode node1 = deque.pop();
            TreeNode node2 = deque.pop();
            //对于左子树
            if (node1.left!=null || node2.left!=null){
                //如果两棵树的左子树都不为空，则加入到队列中继续遍历相加
                if (node1.left!=null && node2.left!=null){
                    TreeNode leftNode = new TreeNode(node1.left.val + node2.left.val);
                    node.left = leftNode;
                    merDeque.addLast(leftNode);
                    deque.addLast(node1.left);
                    deque.addLast(node2.left);
                }
                //如果有其中一个树的左子树为空，则合并后的左子树就是不为空的左子树，不用再进行遍历。
                else if (node1.left==null){
                    node.left = node2.left;
                }
                else if(node2.left==null){
                    node.left = node1.left;
                }
            }
            //对于右子树
            if (node1.right!=null || node2.right!=null){
                if (node1.right!=null && node2.right!=null){
                    //如果两棵树的右子树都不为空，则加入到队列中继续遍历相加
                    TreeNode rightNode = new TreeNode(node1.right.val + node2.right.val);
                    node.right = rightNode;
                    merDeque.addLast(rightNode);
                    deque.addLast(node1.right);
                    deque.addLast(node2.right);
                }
                //如果有其中一个树的右子树为空，则合并后的右子树就是不为空的右子树，不用再进行遍历。
                else if (node1.right==null){
                    node.right = node2.right;
                }
                else if (node2.right==null) {
                    node.right = node1.right;
                }
            }
        }
        return mer;
    }
}