生活随笔
收集整理的这篇文章主要介绍了
leetcode 617. 合并二叉树 思考分析
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
题目
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
思路1：递归遍历两棵树，构造一棵新的树
1、递归参数以及返回值
返回值：新树的结点
参数：两棵旧树
2、终止条件
两棵旧树的对应的该结点都为NULL
3、逻辑（这里直接贴代码和遇到的问题）
首先将情况分为4类：
如果t1 和t2 都是空结点，那么说明新树的这个结点也是NULL
如果t1 t2中一个位空一个不为空，我们可以直接将其中不为空的一个结点的信息直接传给新结点
如果t1 t2全部存在，那么将结点值相加，传给新结点。
注意当进行递归调用traversal时：
如traversal(t1->left,t2->left);：必须要保证t1、t2都不为空，否则编译器会报错。
member access within null pointer of type 'TreeNode'
class Solution {
public:TreeNode
* traversal(TreeNode
* t1
, TreeNode
* t2
){if(t1
== NULL && t2
== NULL) return NULL;int rootVal
=0;if(t1
==NULL && t2
!=NULL) {rootVal
= t2
->val
;TreeNode
* NewRoot
= new TreeNode(rootVal
);NewRoot
->left
= t2
->left
;NewRoot
->right
= t2
->right
;return NewRoot
;}else if(t1
!=NULL && t2
==NULL){rootVal
= t1
->val
;TreeNode
* NewRoot
= new TreeNode(rootVal
);NewRoot
->left
= t1
->left
;NewRoot
->right
= t1
->right
;return NewRoot
;} else{rootVal
= t1
->val
+ t2
->val
;TreeNode
* NewRoot
= new TreeNode(rootVal
);NewRoot
->left
= traversal(t1
->left
,t2
->left
);NewRoot
->right
= traversal(t1
->right
,t2
->right
);return NewRoot
;} }TreeNode
* mergeTrees(TreeNode
* t1
, TreeNode
* t2
) {return traversal(t1
,t2
);}
};
思路2：层序遍历两棵树，构造一棵新的树
在LeetCode 101. 对称二叉树 思考分析中，有过利用队列同时遍历两棵树的经历，这里回顾了一下，然后直接上。
这里完全是基于t1来的，当不重叠的时候，直接将t2的结点直接作为t1的节点，结点与孩子的关系也被传给t1了。
class Solution {
public:TreeNode
* mergeTrees(TreeNode
* t1
, TreeNode
* t2
) {if(t1
== NULL && t2
==NULL) return NULL;else if(t1
== NULL && t2
!=NULL) return t2
;else if(t1
!= NULL && t2
==NULL) return t1
;queue
<TreeNode
*> que
;que
.push(t1
); que
.push(t2
); while(!que
.empty()) {TreeNode
* T1Node
= que
.front();que
.pop();TreeNode
* T2Node
= que
.front();que
.pop();T1Node
->val
+= T2Node
->val
;if(T1Node
->left
&& T2Node
->left
){que
.push(T1Node
->left
);que
.push(T2Node
->left
);}if(T1Node
->right
&& T2Node
->right
){que
.push(T1Node
->right
);que
.push(T2Node
->right
);}if(!T1Node
->left
&& T2Node
->left
){T1Node
->left
= T2Node
->left
;}if(!T1Node
->right
&& T2Node
->right
){T1Node
->right
= T2Node
->right
;}} return t1
;}
};
总结
以上是生活随笔为你收集整理的leetcode 617. 合并二叉树 思考分析的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
