617. 合并二叉树

题目描述

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

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

解题思路

这是一道特征非常明显的简单题。

首先，要想合并两个二叉树，就要先遍历二叉树，所以这道题的基础是数据结构中的二叉树遍历算法。

其次，这道题本身是递归的。“从根节点开始合并两个二叉树”、“从左儿子节点开始合并两个左子树”和“从右儿子节点开始合并两个右子树”这三者的性质是一样的，过程也是一样的。因此本题的 mergeTree 函数可以递归地用在左儿子节点、右儿子节点上。

跳出这道题目本身，可以发现二叉树相关的题目经常直接利用二叉树本身的递归性质。解答这类题目时，脑子里可以这样想来简化思考：

  • 从根节点出发的树是二叉树，那么从左/右儿子节点出发的树也同样是二叉树

  • 如果一个算法能处理根树，那它一定也能处理好左/右子树

  • 如果算法侧重处理左子树，那么可以：

    • 先假设右子树已经被处理好了
    • 解决边界情况，然后具体地处理左子树
    • 递归地调用算法来处理右子树

  • 如果算法侧重处理根树，那么可以：

    • 先假设左右子树都已经被处理好了
    • 解决边界情况，然后具体地处理根节点
    • 递归地调用算法来处理左右子树

回到本题，具体的解决思路大致为：

  • 先假设左右子树都已经处理好了；

  • 解决边界情况，如果左右节点都为 nullptr ，那么直接返回 nullptr ；如果左/右节点为 nullptr ，那么直接返回另一个节点；

  • 具体地处理根节点，更新根节点的 val 为两儿子节点的 val 之和；

  • 递归调用算法来更新根节点的左子树和右子树；

复杂度分析

直接搬运官方的分析

时间复杂度：O(min⁡(m,n))，其中 m 和 n 分别是两个二叉树的节点个数。对两个二叉树同时进行深度优先搜索，只有当两个二叉树中的对应节点都不为空时才会对该节点进行显性合并操作，因此被访问到的节点数不会超过较小的二叉树的节点数。

空间复杂度：O(min⁡(m,n))，其中 m 和 n 分别是两个二叉树的节点个数。空间复杂度取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的最大高度，最坏情况下，二叉树的高度等于节点数。

知识点

递归，二叉树遍历

代码

官方代码

  1. class Solution {
  2. public:
  3.     TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
  4.         if (t1 == nullptr) {
  5.             return t2;
  6.         }
  7.         if (t2 == nullptr) {
  8.             return t1;
  9.         }
  10.         auto merged = new TreeNode(t1->val + t2->val);
  11.         merged->left = mergeTrees(t1->left, t2->left);
  12.         merged->right = mergeTrees(t1->right, t2->right);
  13.         return merged;
  14.     }
  15. };

参考资料

  1. 合并二叉树 Leetcode官方题解