给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
|
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 |
我们看下所有的情况：
我们先分析最简单的情况：T1,T2都是无子节点的树，也就是子节点都是None
那么新节点T3(实际情况我们是将T1的值覆盖为新值，就是NewT1) = T1.val + T2.val
如果稍微复杂一点呢？都有左侧子节点：那么我们先计算根节点：
T1.val = T1.val + T2.val
T1.left = T1.left + T2.left
T1.right = T1.right + T2.right
这个时候我们就完成了，这个时候如果其中一个的左侧节点为None，那么直接返回另外一侧就可以了
那这个问题就转换成一个递归问题了…..
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Solution(object): def mergeTrees(self, t1, t2): """ :type t1: TreeNode :type t2: TreeNode :rtype: TreeNode """ if t1 is None and t2 is None: return None if t1 is None: return t2 if t2 is None: return t1 t1.val = t1.val + t2.val t1.left = self.mergeTrees(t1.left,t2.left) t1.right= self.mergeTrees(t1.right,t2.right) return t1 |
Latest posts by Zhiming Zhang (see all)
- aws eks node 自动化扩展工具 Karpenter - 8月 10, 2022
- ReplicationController and ReplicaSet in Kubernetes - 12月 20, 2021
- public key fingerprint - 5月 27, 2021