题目描述

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为NULL 的节点将直接作为新二叉树的节点。
617. 合并二叉树

解法1 递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null)
            return t2;
        if (t2 == null)
            return t1;
        TreeNode root = new TreeNode(0);
        root.val = t1.val + t2.val;
        root.left = mergeTrees(t1.left, t2.left);
        root.right = mergeTrees(t1.right, t2.right);
        return root;
    }
}

解法2 迭代

class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null || t2 == null) {
            return t1 == null ? t2 : t1;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(t1);
        queue.add(t2);
        while (!queue.isEmpty()) {
            TreeNode tmp1 = queue.remove();
            TreeNode tmp2 = queue.remove();
            tmp1.val += tmp2.val;
            //如果r1和r2的左子树都不为空，就放到队列中
            //如果r1的左子树为空，就把r2的左子树挂到r1的左子树上
            if (tmp1.left != null && tmp2.left != null) {
                queue.add(tmp1.left);
                queue.add(tmp2.left);
            } else if (tmp1.left == null) {
                tmp1.left = tmp2.left;
            }
            if (tmp1.right != null && tmp2.right != null) {
                queue.add(tmp1.right);
                queue.add(tmp2.right);
            } else if (tmp1.right == null) {
                tmp1.right = tmp2.right;
            }
        }
        return t1;
    }
}