西安建筑网站建设,wordpress电影资源,密云城市建设官方网站,仲恺住房和城乡建设局网站给你两棵二叉树#xff1a; root1 和 root2 。
想象一下#xff0c;当你将其中一棵覆盖到另一棵之上时#xff0c;两棵树上的一些节点将会重叠#xff08;而另一些不会#xff09;。你需要将这两棵树合并成一棵新二叉树。合并的规则是#xff1a;如果两个节点重叠#…给你两棵二叉树 root1 和 root2 。
想象一下当你将其中一棵覆盖到另一棵之上时两棵树上的一些节点将会重叠而另一些不会。你需要将这两棵树合并成一棵新二叉树。合并的规则是如果两个节点重叠那么将这两个节点的值相加作为合并后节点的新值否则不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。 示例 1 输入root1 [1,3,2,5], root2 [2,1,3,null,4,null,7]
输出[3,4,5,5,4,null,7]示例 2
输入root1 [1], root2 [1,2]
输出[2,2]
class Solution {
public:TreeNode* dfs(TreeNode* root1,TreeNode* root2){//这两个if返回值很巧妙。两者只有其一就返回这个节点。if(!root1) return root2;if(!root2) return root1;TreeNode* root new TreeNode(0);root-val root1-val root2-val;root-left dfs(root1-left,root2-left);root-right dfs(root1-right,root2-right);return root;}TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if(!root1 !root2) return nullptr;return dfs(root1,root2);}
};//bfs
class Solution {
public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {//迭代queueTreeNode*que;if(!root1) return root2;if(!root2) return root1;que.push(root1);que.push(root2);while(!que.empty()){TreeNode* node1 que.front();que.pop();TreeNode* node2 que.front();que.pop();node1-val node2-val;if(node1-left node2-left){que.push(node1-left);que.push(node2-left);}if(node1-right node2-right){que.push(node1-right);que.push(node2-right);}if(!node1-left node2-left){node1-left node2-left;}if(!node1-right node2-right){node1-right node2-right;}}return root1;}
};
