Skip to content

Commit c955658

Browse files
da183da183
committed
binary search tree
1 parent 07a404c commit c955658

File tree

1 file changed

+85
-91
lines changed

1 file changed

+85
-91
lines changed

‎advanced_algorithm/binary_search_tree.md‎

Lines changed: 85 additions & 91 deletions
Original file line numberDiff line numberDiff line change
@@ -11,125 +11,119 @@
1111

1212
> 验证二叉搜索树
1313
14-
```go
15-
/**
16-
* Definition for a binary tree node.
17-
* type TreeNode struct {
18-
* Val int
19-
* Left *TreeNode
20-
* Right *TreeNode
21-
* }
22-
*/
23-
func isValidBST(root *TreeNode) bool {
24-
return dfs(root).valid
25-
}
26-
type ResultType struct{
27-
max int
28-
min int
29-
valid bool
30-
}
31-
func dfs(root *TreeNode)(result ResultType){
32-
if root==nil{
33-
result.max=-1<<63
34-
result.min=1<<63-1
35-
result.valid=true
36-
return
37-
}
14+
```c++
15+
class Solution {
16+
public:
17+
struct Result {
18+
TreeNode *maxNode;
19+
TreeNode *minNode;
20+
bool isValidate;
3821

39-
left:=dfs(root.Left)
40-
right:=dfs(root.Right)
22+
Result(bool validate = true, TreeNode *max = nullptr, TreeNode *min = nullptr)
23+
: isValidate(validate), maxNode(max), minNode(min) {
4124

42-
// 1、满足左边最大值<root<右边最小值 && 左右两边valid
43-
if root.Val>left.max && root.Val<right.min && left.valid && right.valid {
44-
result.valid=true
45-
}
46-
// 2、更新当前节点的最大最小值
47-
result.max=Max(Max(left.max,right.max),root.Val)
48-
result.min=Min(Min(left.min,right.min),root.Val)
49-
return
50-
}
51-
func Max(a,b int)int{
52-
if a>b{
53-
return a
54-
}
55-
return b
56-
}
57-
func Min(a,b int)int{
58-
if a>b{
59-
return b
25+
}
26+
};
27+
bool isValidBST(TreeNode *root) {
28+
if (!root) {
29+
return true;
30+
}
31+
return helper(root).isValidate;
6032
}
61-
return a
62-
}
6333

34+
Result helper(TreeNode *root) {
35+
if (!root) {
36+
return {};
37+
}
38+
auto left = helper(root->left);
39+
auto right = helper(root->right);
40+
if (!(left.isValidate && right.isValidate)) {
41+
return {false};
42+
}
43+
if (left.maxNode && left.maxNode->val >= root->val) {
44+
return {false};
45+
}
46+
if (right.minNode && right.minNode->val <= root->val) {
47+
return {false};
48+
}
49+
return {
50+
true,
51+
right.maxNode ? right.maxNode : root,
52+
left.minNode ? left.minNode : root,
53+
};
54+
}
55+
};
6456
```
6557
6658
[insert-into-a-binary-search-tree](https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/)
6759
6860
> 给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。
6961
70-
```go
71-
func insertIntoBST(root *TreeNode, val int) *TreeNode {
72-
if root==nil{
73-
return &TreeNode{Val:val}
62+
```c++
63+
TreeNode *insertIntoBST(TreeNode *root, int val) {
64+
if (root == nullptr) {
65+
return new TreeNode(val);
7466
}
75-
if root.Val<val{
76-
root.Right=insertIntoBST(root.Right,val)
77-
}else{
78-
root.Left=insertIntoBST(root.Left,val)
67+
if (root->val > val) {
68+
root->left = insertIntoBST(root->left, val);
69+
} else {
70+
root->right = insertIntoBST(root->right, val);
7971
}
80-
return root
72+
return root;
8173
}
8274
```
8375

8476
[delete-node-in-a-bst](https://leetcode-cn.com/problems/delete-node-in-a-bst/)
8577

8678
> 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的  key  对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
8779
88-
```go
89-
/**
90-
* Definition for a binary tree node.
91-
* type TreeNode struct {
92-
* Val int
93-
* Left *TreeNode
94-
* Right *TreeNode
95-
* }
96-
*/
97-
func deleteNode(root *TreeNode, key int) *TreeNode {
98-
// 删除节点分为三种情况：
99-
// 1、只有左节点 替换为右
100-
// 2、只有右节点 替换为左
101-
// 3、有左右子节点 左子节点连接到右边最左节点即可
102-
if root ==nil{
103-
return root
80+
```c++
81+
// 注意二叉搜索树的概念！
82+
// 如果当前节点是其父节点的左子节点，则当前节点底下任何一个节点都要比该父节点小
83+
// 反之亦然
84+
TreeNode* deleteNode(TreeNode* root, int key) {
85+
if (root == nullptr) {
86+
return root;
10487
}
105-
if root.Val<key{
106-
root.Right=deleteNode(root.Right,key)
107-
}else if root.Val>key{
108-
root.Left=deleteNode(root.Left,key)
109-
}else if root.Val==key{
110-
if root.Left==nil{
111-
return root.Right
112-
}else if root.Right==nil{
113-
return root.Left
114-
}else{
115-
cur:=root.Right
116-
// 一直向左找到最后一个左节点即可
117-
for cur.Left!=nil{
118-
cur=cur.Left
119-
}
120-
cur.Left=root.Left
121-
return root.Right
122-
}
88+
if (root->val < key) {
89+
root->right = deleteNode(root->right, key);
90+
return root;
91+
}
92+
if (root->val > key) {
93+
root->left = deleteNode(root->left, key);
94+
return root;
95+
}
96+
// 每个节点中的值必须大于（或等于）存储在其左侧子树中的任何值。
97+
// 所以压根不需要考虑啥当前节点的父节点，必定当前节点的左右子树！
98+
if (root->left == nullptr) {
99+
return root->right;
123100
}
124-
return root
101+
if (root->right == nullptr) {
102+
return root->left;
103+
}
104+
auto iter = root->right;
105+
while (iter->left != nullptr) {
106+
iter = iter->left;
107+
}
108+
iter->left = root->left;
109+
return root->right;
125110
}
126111
```
127112
128113
[balanced-binary-tree](https://leetcode-cn.com/problems/balanced-binary-tree/)
129114
130115
> 给定一个二叉树，判断它是否是高度平衡的二叉树。
131116
132-
```go
117+
```c++
118+
struct ResultType {
119+
int height;
120+
bool valid;
121+
};
122+
123+
bool isBalanced(TreeNode *root) {
124+
return dfs(root).valid;
125+
}
126+
133127
type ResultType struct{
134128
height int
135129
valid bool

0 commit comments

Comments
 (0)