首页 » 运维 » puppet » 正文

leetCode617并二叉树(Merge Two Binary Trees) python

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

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

我们看下所有的情况:

617

 

我们先分析最简单的情况: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,那么直接返回另外一侧就可以了

那这个问题就转换成一个递归问题了…..

 

发表评论