删除二叉树的子树:假设二叉树中的结点均不相等,采用二叉链存储,设计递归算法删除根结点值为x的子树。
时间: 2023-04-01 18:01:31 浏览: 157
可以回答这个问题。递归删除根结点值为x的子树的算法如下:
1. 如果当前结点为空,则返回空。
2. 如果当前结点的值等于x,则将左右子树都置为空,返回空。
3. 递归删除左子树中值为x的子树。
4. 递归删除右子树中值为x的子树。
5. 如果当前结点的左子树不为空且值等于x,则将左子树置为空。
6. 如果当前结点的右子树不为空且值等于x,则将右子树置为空。
7. 返回当前结点。
代码实现如下:
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
};
TreeNode* deleteSubtree(TreeNode* root, int x) {
if (root == nullptr) {
return nullptr;
}
if (root->val == x) {
root->left = nullptr;
root->right = nullptr;
return nullptr;
}
root->left = deleteSubtree(root->left, x);
root->right = deleteSubtree(root->right, x);
if (root->left != nullptr && root->left->val == x) {
root->left = nullptr;
}
if (root->right != nullptr && root->right->val == x) {
root->right = nullptr;
}
return root;
}
阅读全文