LeetCode450 删除二叉搜索树中的节点

链接: https://leetcode-cn.com/problems/recover-binary-search-tree

题意

给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变

解法

一开始想了很久一直想不到解题的思路
后来经过仔细分析搜索树的性质想到
如果要删除一个节点 它一定是某棵子树的根节点
左子树中所有节点小于它,同时小于所有右子树上的节点
那么可以把它的左节点或右节点都可以作为新的根节点
如果把左节点设为新的根,则需要把左节点的右节点进行处理(移到右子树中的最左边)
反之,需要把右节点的左节点进行处理(移到左子树的最右边)
写出了一串很长的代码,新定义了四个函数
重新思考后,写出了简化后的版本,细节见代码

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
TreeNode* insert(TreeNode* root, TreeNode* add) {
if (add == nullptr) return root; // 如果要插入的节点为nullptr 直接返回root
if (root == nullptr) return add; // 如果要root为nullptr 直接返回插入节点
if (root -> val < add -> val) { // 根据root和add的大小关系进行插入
root -> right = insert(root -> right, add);
}
else {
root -> left = insert(root -> left, add);
}
return root;
}
TreeNode* construct(TreeNode* root) {
if (root -> left) { // 如果存在左节点 将左节点作为根节点
TreeNode* add = root -> left -> right;
root -> left -> right = root -> right;
root = root -> left;
root = insert(root, add);
}
else if (root -> right){ // 如果存在右节点 将右节点作为根节点
TreeNode* add = root -> right -> left;
root -> right -> left = root -> left;
root = root -> right;
root = insert(root, add);
}
else {
root = nullptr; // 如果左右都不存在 说明树中只存在一个根节点
}
return root;
}
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) return root;
if (root -> val == key) {
return construct(root);
}
root -> left = deleteNode(root -> left, key);
root -> right = deleteNode(root -> right, key);
return root;
}
};