问题

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

示例 1:

输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/ \
4 5
/ \ \
5 4 7
注意: 合并必须从两个树的根节点开始

解法一：递归

  • 确定递归函数的参数和返回值

    • 首先那么要合入两个二叉树，那么参数至少是要传入两个二叉树的根节点，返回值就是合并之后二叉树的根节点
      1. TreeNode mergeTrees(TreeNode t1, TreeNode t2) {

  • 确定终止条件：

    • 因为是传入了两个树，那么就有两个树遍历的节点t1和t2，如果t1 == null，两个树合并就应该是t2 （如果t2也为null也无所谓，合并之后就是null）
    • 反过来如果t2 == null，那么两个数合并就是t1（如果t1也为null也无妨，合并之后就是null）
      1. if (t1 == null) return t2; // 如果t1为空，合并之后就应该是t2
      2. if (t2 == null) return t1; // 如果t2为空，合并之后就应该是t1

  • 确定单层递归的逻辑：

    • 单层递归的逻辑就比较好些了，这里我们用重复利用一下t1这个树，t1就是合并之后树的根节点（就是修改了原来树的结构） ，那么单层递归中，就要把两棵树的元素加到一起

      1. t1.val += t2.val;

    • 接下来t1的左子树是：合并t1左子树t2左子树之后的左子树

    • t1的右子树：是合并t1右子树t2右子树之后的右子树
    • 最终t1就是合并之后的根节点
      1. t1.left = mergeTrees(t1.left, t2.left);
      2. t1.right = mergeTrees(t1.right, t2.right);
      3. return t1;

前序遍历

  1. class Solution {
  2.     TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
  3.         if (t1 == null) 
  4.             return t2; // 如果t1为空，合并之后就应该是t2
  5.         if (t2 == null) 
  6.             return t1; // 如果t2为空，合并之后就应该是t1
  7.         // 修改了t1的数值和结构
  8.         t1.val += t2.val;                             // 中
  9.         t1.left = mergeTrees(t1.left, t2.left);      // 左
  10.         t1.right = mergeTrees(t1.right, t2.right);   // 右
  11.         return t1;
  12.     }
  13. }

也可以不修改t1和t2的数据结构，重新定义一个树

  1. class Solution {
  2.     TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
  3.         if (t1 == null) 
  4.             return t2; // 如果t1为空，合并之后就应该是t2
  5.         if (t2 == null) 
  6.             return t1; // 如果t2为空，合并之后就应该是t1
  7.         // 修改了t1的数值和结构
  8.         TreeNode root = new TreeNode(0);
  9.         root.val = t1.val + t2.val;                         
  10.         root.left = mergeTrees(t1.left, t2.left);      
  11.         root.right = mergeTrees(t1.right, t2.right);   
  12.         return root;
  13.     }
  14. }

解法二：层序遍历

  1. class Solution {
  2.     TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
  3.         if (t1 == null) 
  4.             return t2;
  5.         if (t2 == null) 
  6.             return t1;
  8.         Queue<TreeNode> queue = new LinkedList<TreeNode>();
  9.         queue.offer(t1);
  10.         queue.offer(t2);
  11.         while(!queue.isEmpty()) {
  12.             TreeNode node1 = queue.poll(); 
  13.             TreeNode node2 = queue.poll();
  14.             // 此时两个节点一定不为空，val相加
  15.             node1.val += node2.val;
  17.             // 如果两棵树左节点都不为空，加入队列
  18.             if (node1.left != null && node2.left != null) {
  19.                 queue.offer(node1.left);
  20.                 queue.offer(node2.left);
  21.             }
  23.             // 如果两棵树右节点都不为空，加入队列
  24.             if (node1.right != null && node2.right != null) {
  25.                 queue.offer(node1.right);
  26.                 queue.offer(node2.right);
  27.             }
  29.             // 当t1的左节点为空 t2左节点不为空，就赋值过去
  30.             if (node1.left == null && node2.left != null) {
  31.                 node1.left = node2.left;
  32.             }
  33.             // 当t1的右节点 为空 t2右节点不为空，就赋值过去
  34.             if (node1.right == null && node2.right != null) {
  35.                 node1.right = node2.right;
  36.             }
  37.         }
  38.         return t1;
  39.     }
  40. }