合并二叉树

题目描述

力扣链接🔗

合并二叉树 - 图1

代码分析

递归法

前序递归流程图：

合并二叉树 - 图2

此题可以构造一棵新的树来返回，但为了节约资源，可以使用树1进行修改即可。

  • 确认返回值和参数
    返回值为TreeNode，因为需要将二叉树和并，并返回其中的根节点，所以返回值需要为TreeNode，因为需要遍历2棵树，所以参数为2棵树，

  • 确认中止条件
    当一棵树的左节点有值，而另一棵树的节点没有值，那么返回有值的那棵树的节点，不用再次递归。

  • 单层循环逻辑
    单层循环中，两棵树都有值，那么需要将2棵树合并在一起。

代码:

三种递归都可以

  1. /**
  2.  * 递归法（前序）
  3.  * @param root1
  4.  * @param root2
  5.  * @return
  6.  */
  7. public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
  8.     // 为空直接返回一个节点即可，不用在递归
  9.     if (root1 == null) return root2;
  10.     if (root2 == null) return root1;
  12.     root1.val += root2.val; // 将root1作为结果，节约资源，中
  13.     root1.left = mergeTrees(root1.left, root2.left);
  14.     root1.right = mergeTrees(root1.right, root2.right);
  16.     return root1;
  17. }
  19. /**
  20.  * 递归法（中序）
  21.  *
  22.  * @param root1
  23.  * @param root2
  24.  * @return
  25.  */
  26. public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
  27.     // 为空直接返回一个节点即可，不用在递归
  28.     if (root1 == null) return root2;
  29.     if (root2 == null) return root1;
  31.     root1.left = mergeTrees(root1.left, root2.left);    // 左
  32.     root1.val += root2.val; // 将root1作为结果，节约资源，中
  33.     root1.right = mergeTrees(root1.right, root2.right); // 右
  35.     return root1;
  36. }
  38. /**
  39.  * 递归法（中序）
  40.  *
  41.  * @param root1
  42.  * @param root2
  43.  * @return
  44.  */
  45. public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
  46.     // 为空直接返回一个节点即可，不用在递归
  47.     if (root1 == null) return root2;
  48.     if (root2 == null) return root1;
  50.     root1.left = mergeTrees(root1.left, root2.left);    // 左
  51.     root1.right = mergeTrees(root1.right, root2.right); // 右
  52.     root1.val += root2.val; // 将root1作为结果，节约资源，中
  54.     return root1;
  55. }

迭代法

使用层序遍历，同对称二叉树的迭代法思路大致一致，需要将2个节点入队进行判断。判断详情见注释。

  1. /**
  2.  * 迭代法
  3.  *
  4.  * @param root1
  5.  * @param root2
  6.  * @return
  7.  */
  8. public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
  9.     // 判断2棵树第一个元素
  10.     if (root1 == null) return root2;
  11.     if (root2 == null) return root1;
  12.     Queue<TreeNode> queue = new LinkedList<>();
  13.     queue.offer(root1);
  14.     queue.offer(root2);
  16.     while (!queue.isEmpty()) {
  17.         TreeNode node1 = queue.poll();
  18.         TreeNode node2 = queue.poll();
  20.         node1.val += node2.val; // 此时2个节点一定不为null
  22.         // 如果2个节点的左节点都不为空，那么都加入节点
  23.         if (node1.left != null && node2.left != null) {
  24.             queue.offer(node1.left);
  25.             queue.offer(node2.left);
  26.         }
  28.         // 如果2个节点的右节点都不为空，那么都加入节点
  29.         if (node1.right != null && node2.right != null) {
  30.             queue.offer(node1.right);
  31.             queue.offer(node2.right);
  32.         }
  34.         // 当t1的左节点 为空 t2左节点不为空，就赋值过去
  35.         if (node1.left == null && node2.left != null) {
  36.             node1.left = node2.left;    // 此时不再入队
  37.         }
  39.         // 当t1的右节点 为空 t2右节点不为空，就赋值过去
  40.         if (node1.right == null && node2.right != null) {
  41.             node1.right = node2.right;
  42.         }
  44.         // 如果左节点为空，右节点不为空的话，因为最后以root1作为返回结果，所以不需要在进行判断
  45.     }
  46.     return root1;
  47. }