将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则,不为NULL的节点将直接作为新二叉树的节点。
方法1:使用递归
递归三部曲:
(1)参数和返回值:参数为两个二叉树的根结点,返回值为合并后二叉树的根结点。
(2)确定终止条件:两个节点其中一个为零,直接返回不为零的结点。
(3)单层递归的逻辑。
具体实现代码如下:
//递归法
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
//确定终止条件
if (root1 == NULL) return root2;
if (root2 == NULL) return root1;
//单层递归的逻辑
root1->val += root2->val;
root1->left = mergeTrees(root1->left, root2->left);
root1->right = mergeTrees(root1->right, root2->right);
return root1;
}
方法2:迭代法
将两棵树的结点同时放入队列中进行比较。
//迭代法
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if(root1 == NULL) return root2;
if(root2 == NULL) return root1;
queue<TreeNode*> que;
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 && node->left) {
node1->left = node2->left;
}
if(!node1->right && node->right) {
node1->right = node2->right;
}
}
return t1;
}