树：BST & Inorder
睡不醒的鲤鱼 2022-04-13 每日一题 LeetCode
# 0098. 验证二叉搜索树 (opens new window)
题目
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
对二叉树进行中序遍历，每遍历到一个节点都和当前已遍历的最后一个节点值比较，只要能满足递增关系就继续遍历，直到遍历所有节点。
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
long long lastVal = LLONG_MIN;
public:
bool isValidBST(TreeNode* root) {
if (!root) return true;
if (!isValidBST(root->left)) {
return false;
}
if (root->val <= lastVal) return false;
lastVal = root->val;
return isValidBST(root->right);
}
};
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
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
# 0099. 恢复二叉搜索树 (opens new window)
题目
给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。
Morris 遍历 + 寻找逆序对。
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
TreeNode *first = nullptr, *second = nullptr;
public:
void recoverTree(TreeNode* root) {
TreeNode *last = nullptr, *cur = root;
while (cur) {
if (!cur->left) {
check(last, cur);
last = cur;
cur = cur->right;
} else {
TreeNode *p = cur->left;
while (p->right && p->right != cur) p = p->right;
if (!p->right) p->right = cur, cur = cur->left;
else {
p->right = nullptr;
check(last, cur);
last = cur;
cur = cur->right;
}
}
}
swap(first->val, second->val);
}
void check(TreeNode *last, TreeNode *cur) {
if (last && last->val > cur->val) {
if (!first) first = last, second = cur;
else second = cur;
}
}
};
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
42
43
44
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
42
43
44
# 0108. 将有序数组转换为二叉搜索树 (opens new window)
题目
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
每次选择中间节点作为根节点，然后递归对左右子树构造即可。
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return build(nums, 0, nums.size() - 1);
}
TreeNode* build(vector<int>& nums, int l, int r) {
if (l > r) return nullptr;
int mid = l + (r - l) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = build(nums, l, mid - 1);
root->right = build(nums, mid + 1, r);
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
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
# 0109. 有序链表转换二叉搜索树 (opens new window)
题目
给定一个单链表的头节点 head ，其中的元素 按升序排序 ，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。
本题同 0108. 将有序数组转换为二叉搜索树 思路一致，只是获取中间节点需要使用快慢指针来实现。
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* sortedListToBST(ListNode* head) {
if (!head) return nullptr;
if (!head->next) return new TreeNode(head->val);
ListNode *midNode = getMidNode(head);
TreeNode *root = new TreeNode(midNode->val);
root->left = sortedListToBST(head);
root->right = sortedListToBST(midNode->next);
return root;
}
ListNode* getMidNode(ListNode* head) {
ListNode *pre = nullptr;
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
fast = fast->next->next;
pre = slow;
slow = slow->next;
}
if (pre) pre->next = nullptr;
return slow;
}
};
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
42
43
44
45
46
47
48
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
42
43
44
45
46
47
48
# 0173. 二叉搜索树迭代器 (opens new window)
题目
解析
代码
# 0230. 二叉搜索树中第K小的元素 (opens new window)
题目
解析
代码
# 0235. 二叉搜索树的最近公共祖先 (opens new window)
题目
解析
代码
# 0270. 最接近的二叉搜索树值 (opens new window)
题目
解析
代码
# 0272. 最接近的二叉搜索树值 II (opens new window)
题目
解析
代码
# 0285. 二叉搜索树中的中序后继 (opens new window)
题目
解析
代码
# 0297. 二叉树的序列化与反序列化 (opens new window)
题目
解析
代码
# 0426. 将二叉搜索树转化为排序的双向链表 (opens new window)
题目
解析
代码
# 0449. 序列化和反序列化二叉搜索树 (opens new window)
题目
解析
代码
# 0450. 删除二叉搜索树中的节点 (opens new window)
题目
解析
代码
# 0501. 二叉搜索树中的众数 (opens new window)
题目
解析
代码
# 0510. 二叉搜索树中的中序后继 II (opens new window)
题目
解析
代码
# 0530. 二叉搜索树的最小绝对差 (opens new window)
题目
解析
代码
# 0538. 把二叉搜索树转换为累加树 (opens new window)
题目
解析
代码