Day18 | Part8
约 169 个字 59 行代码 预计阅读时间 1 分钟
利用二叉搜索树中序是有序的,故公共祖先一定在两者中间
递归:
| TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root->val > p->val && root->val > q->val)
return lowestCommonAncestor(root->left, p, q);
else if(root->val < p->val && root->val < q->val)
return lowestCommonAncestor(root->right, p, q);
return root;
}
|
迭代:
| TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
while(root) {
if(root->val > p->val && root->val > q->val) root = root->left;
else if(root->val < p->val && root->val < q->val) root = root->right;
else return root;
}
return nullptr;
}
|
| TreeNode* insertIntoBST(TreeNode* root, int val) {
if(!root) {
auto node = new TreeNode(val);
return node;
}
if(root->val > val) root->left = insertIntoBST(root->left, val);
else if(root->val < val) root->right = insertIntoBST(root->right, val);
return root;
}
|
先找,若没找到直接返回, 若找到了,几种情况
- 左右都空,直接删除
- 左空右不空，删除后,右孩子补位, 返回右孩子
- 左不空右空, 删除后,左孩子补位, 返回左孩子
- 左右都不空, 将删除左子树的头节点放到删除节点的右子树最左边的左孩子上, 返回删除节点右孩子 → 动图
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 | TreeNode* deleteNode(TreeNode* root, int key) {
if(!root) return root; // 没找到
if(root->val == key) {
// 左右都空
if(!root->left && !root->right) {
delete root;
return nullptr;
}
// 左空右不空
else if(!root->left && root->right) {
auto tmp = root->right;
delete root;
return tmp;
}
// 左不空右空
else if(root->left && !root->right) {
auto tmp = root->left;
delete root;
return tmp;
}
// 左右都不空
else {
auto cur = root->right; // 找右子树最左边的节点
while(cur->left) cur = cur->left;
cur->left = root->left; //删除节点的左放到右的最左边
auto tmp = root; // 暂存root, 删除
root = root->right;
delete tmp;
return root;
}
}
if(root->val > key) root->left = deleteNode(root->left, key);
if(root->val < key) root->right = deleteNode(root->right, key);
return root;
}
|
