问题是:
给定两棵二叉树,想象一下,当您将其中一棵树覆盖在另一棵树上时,两棵树的某些节点重叠而其他节点不重叠。
你需要将它们合并成一个新的二叉树。合并规则是,如果两个节点重叠,则将节点值相加作为合并节点的新值。否则,NOT null节点将被用作新树的节点。
Example 1:
Input:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
Output:
Merged tree:
3
/ \
4 5
/ \ \
5 4 7
注意:合并过程必须从两棵树的根节点开始。
我尝试解决这个 leetcode 问题,但总是得到错误的答案。
我的答案是:
**Merged tree:
3
/ \
4 5
/
5**
我好像丢了节点4和节点7。
但是,从 std::cout 来看,所有节点都已创建,但树似乎并未构建。
我非常感谢对我的代码的任何评论:
class Solution {
public:
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if (t1 == NULL && t2 == NULL)
return NULL;
else if (t1 == NULL && t2 != NULL) {
t1 = new TreeNode(t2->val);
cout << "vq1:" << t1->val << endl;
mergeTrees(t1->left, t2->left);
mergeTrees(t1->right, t2->right);
}
else if (t1 != NULL && t2 == NULL) {
t1->val += 0;
cout << "vu1:" << t1->val << endl;
mergeTrees(t1->left, NULL);
mergeTrees(t1->right, NULL);
}
else if (t1 != NULL && t2 != NULL) {
t1->val += t2->val;
cout << "vx1:" << t1->val << endl;
mergeTrees(t1->left, t2->left);
mergeTrees(t1->right, t2->right);
}
return t1;
}
};
最佳答案
你正在更新节点而不是节点的左右子节点试试这个,
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if (t1 == NULL && t2 == NULL)
return NULL;
else if (t1 == NULL && t2 != NULL) {
t1 = new TreeNode(t2->val);
cout << "vq1:" << t1->val << endl;
t1->left = mergeTrees(t1->left, t2->left);
t1->right = mergeTrees(t1->right, t2->right);
}
else if (t1 != NULL && t2 == NULL) {
t1->val += 0;
cout << "vu1:" << t1->val << endl;
t1->left = mergeTrees(t1->left, NULL);
t1->right = mergeTrees(t1->right, NULL);
}
else if (t1 != NULL && t2 != NULL) {
t1->val += t2->val;
cout << "vx1:" << t1->val << endl;
t1->left = mergeTrees(t1->left, t2->left);
t1->right = mergeTrees(t1->right, t2->right);
}
return t1;
}
关于c++ - LeetCode #617 "Merge Two Binary Trees"使用 C++,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48902798/