合并二叉树

题目

合并二叉树（力扣：617）

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

分析

合并两个二叉树，可以使用递归和遍历两种方式求解。

递归求解：两个二叉树t1、t2中，如果一个为空，则返回另一个；将t1的值修改为t1的值+t2的值；递归，让t1的left等于合并后的t1.left和t2.left，右子树同理；最后返回t1。
遍历求解：也可以使用遍历的方式求解。遍历两颗二叉树，将二叉树每个节点的值相加即可。

代码实现：递归

    /**
     * 617. 合并二叉树
     * @param t1
     * @param t2
     * @return
     */
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if(t1 == null || t2 == null){
            return t1 == null ? t2 : t1;
        }
        t1.val += t2.val;
        t1.left = mergeTrees(t1.left, t2.left);
        t1.right = mergeTrees(t1.right, t2.right);
        return t1;
    }

扩展：不修改原二叉树解法。

    /**
     * 617. 合并二叉树   不修改原树
     * @param t1
     * @param t2
     * @return
     */
    public TreeNode mergeTrees2(TreeNode t1, TreeNode t2) {
        if(t1 == null && t2 == null){
            return null;
        }
        TreeNode node = new TreeNode((t1 != null ? t1.val : 0) + (t2 != null ? t2.val : 0));
        node.left = mergeTrees2(t1 != null ? t1.left : null, t2 != null ? t2.left:null);
        node.right = mergeTrees2(t1 != null ? t1.right : null, t2 != null ? t2.right:null);
        return node;
    }

代码实现：层序遍历

    /**
     * 617. 合并二叉树
     * @param t1
     * @param t2
     * @return
     */
    public TreeNode mergeTrees2(TreeNode t1, TreeNode t2) {
        if(t1 == null){
            return t2;
        }
        if (t2 == null){
            return t1;
        }
        LinkedList<TreeNode> linkedList = new LinkedList<>();
        linkedList.add(t1);
        linkedList.add(t2);
        while (!linkedList.isEmpty()){
            TreeNode n1 = linkedList.poll();
            TreeNode n2 = linkedList.poll();
            n1.val = n1.val + n2.val;
            if (n1.left != null && n2.left != null){
                linkedList.add(n1.left);
                linkedList.add(n2.left);
            }else if (n1.left == null){
                n1.left = n2.left;
            }
            if (n1.right != null && n2.right != null){
                linkedList.add(n1.right);
                linkedList.add(n2.right);
            }else if (n1.right == null){
                n1.right = n2.right;
            }
        }
        return t1;
    }