东莞网站设计开发技能大赛,中国企业网,做网站自适应框架,python 做的网站有哪些题目
给定两个二叉树#xff0c;想象当你将它们中的一个覆盖到另一个上时#xff0c;两个二叉树的一些节点便会重叠。 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠#xff0c;那么将他们的值相加作为节点合并后的新值#xff0c;否则不为 NULL 的节点…题目
给定两个二叉树想象当你将它们中的一个覆盖到另一个上时两个二叉树的一些节点便会重叠。 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠那么将他们的值相加作为节点合并后的新值否则不为 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
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* traversal(TreeNode* t1, TreeNode* t2){if(t1 NULL t2 NULL) return NULL;int rootVal0;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 t2NULL){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 t2NULL) return NULL;else if(t1 NULL t2!NULL) return t2;else if(t1 ! NULL t2NULL) return t1;queueTreeNode* 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);}//当t1的某个结点为空时且t2的结点不为空不入队列//当t1左结点为空t2左结点不为空if(!T1Node-left T2Node-left){T1Node-left T2Node-left;}if(!T1Node-right T2Node-right){T1Node-right T2Node-right;}} return t1;}
};
