心之所向便是光

Leetcode 617.合并二叉树

  • 2021-08-18
  • 作者 Ender
  • 1448 字
  • 次阅读

题目描述：

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

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

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
输出: 
合并后的树:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7

注意: 合并必须从两个树的根节点开始。

链接：

https://leetcode-cn.com/problems/merge-two-binary-trees

题目分析

  我们递归地处理节点就可以。把 Tree 1 作为主树，将 Tree 2 合并到 Tree 1 过来。若 Tree 1 为空则可以直接返回 Tree 2（不管是否为空都是正确的）。若 Tree 1 不为空则判断 Tree 2 是否也不为空，均不为空的话就将 Tree 2 的值加到 Tree 1 上，递归地处理它们的子树，然后返回 Tree 1。若 Tree 2 为空直接返回 Tree 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1 == nullptr){
            return root2;
        }
        else if(root2 != nullptr){
            root1->val += root2->val;
            root1->left = mergeTrees(root1->left, root2->left);
            root1->right = mergeTrees(root1->right, root2->right);
        }
        return root1;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 是二叉树的节点数。我们对两个二叉树进行了一次遍历。
  空间复杂度：$O(1)$。我们只是处理结点值并且连接树，没有用到额外的变量。

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
, ,
最后编辑：2021-08-18