BST 的性质
1.对于 BST 的任意一个根节点, 左子树的所有值都比根节点小, 右子树节点都比根节点大
2.对于 BST 的任意一个根节点, 它的左右子树都是 BST
3.因 BST 的定义, BST 中序遍历是节点排序的结果, 很多和 BST 排序相关的问题, 都要用到中序遍历的性质
4.BST 比较重要, AVL/红黑树/B+树/线段树都是基于 BST
230.二叉搜索树中第K小的元素
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
示例 1：输入：root = [3,1,4,null,2], k = 1 输出：1
示例 2：输入：root = [5,3,6,2,4,null,null,1], k = 3 输出：3
分析:
1.BST中序遍历正好是有序的, 因此采用中序遍历, 找到遍历数 == k 的时候, 返回, 先用递归版本
class Solution {
private:
int ans = 0;
int rank = 0;
public:
void traverse(TreeNode* root, int k) {
if (root == nullptr) {
return;
}
// 前序位置
traverse(root->left, k);
// 搜到中序位置
++rank;
if (k == rank) {
ans = root->val;
return;
}
// 后序位置
traverse(root->right, k);
}
int kthSmallest(TreeNode* root, int k) {
traverse(root, k);
return ans;
}
};
同时顺便写一下迭代版本的中序遍历搜索
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
stack<TreeNode*> s;
while (root != nullptr || !s.empty()) {
while (root != nullptr) {
s.push(root);
root = root->left;
}
root = s.top();
s.pop();
--k;
if (k == 0) {
return root->val;
}
root = root->right;
}
return 0;
}
};
2.假如我们频繁地查找第 k 小的值, 有没有优化方法? 我们每次采用重新中序遍历的一个前提是不知道每个根节点的子树的节点总数, 假设我们已经知道了每个根节点的左子树的以某个节点的子树节点总数为 nodeNum, 可以先用左子树的节点数和我们要找的 k 进行比较, 判定是否在左子树里面, 或者在右子树里面, 还是直接就是当前根节点就是第 k 小的树
3.令 node 为当前根节点开始搜索, 也就是说一开始指针指向 root,
如果 node 的左子树的节点数 leftNodeNum < k-1, 那么第 k 小的元素在 node 的右子树中, 指针搜向右边的子树 node=node->right, 搜索的空间可以直接减去 (leftNodeNums + 1), 然后继续搜索
如果 node 的左子树的节点数 leftNodeNum == k-1, 那么第 k 小的元素就是 node 直接返回 node
如果 node 的左子树的节点数 leftNodeNum > k-1, 那么第 k 小的元素在node的左子树里面, 指针走向左子树里面搜索 node=node->left, 继续搜索
3.为实现上述的逻辑, 先将每个根节点数保存在哈希表中
class Solution {
public:
unordered_map<TreeNode*, int> nodeNum;
// 记录以 node 为根节点的树的节点总数
int countNodesNum(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int num = 1 + countNodesNum(root->left) + countNodesNum(root->right);
nodeNum[root] = num;
return num;
}
int kthSmallest(TreeNode* root, int k) {
if (root == nullptr) {
return 0;
}
countNodesNum(root);
while (root != nullptr) {
int leftNodeNum = nodeNum[root->left];
if (leftNodeNum < k - 1) {
root = root->right;
k -= leftNodeNum + 1;
} else if (leftNodeNum == k - 1) {
return root->val;
} else if (leftNodeNum > k - 1) {
root = root->left;
}
}
return root->val;
}
};
1038.从二叉搜索树到更大和树
给定一个二叉搜索树 root (BST)，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。
提醒一下， 二叉搜索树 满足下列约束条件：
节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。示例 1：输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] 输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
示例 2：输入：root = [0,null,1] 输出：[1,null,1]
分析:
1.题目中要大于等于该节点的所有节点值之和; 值大于或者等于该节点值, 对于二叉搜索数来说, 其实就是根节点+右子树求和;
2.这道题采用一个反序的中序遍历, 也就是右孩子->根节点->左孩子, 然后可以递归的累加右子树的所有和
class Solution {
private:
int sum = 0;
public:
TreeNode* bstToGst(TreeNode* root) {
if (root == nullptr) {
return nullptr;
}
bstToGst(root->right);
sum += root->val;
root->val = sum;
bstToGst(root->left);
return root;
}
};
538.把二叉搜索树转换为累加树
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。示例 1：输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] 输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
示例 2：输入：root = [0,null,1] 输出：[1,null,1]
示例 3：输入：root = [1,0,2] 输出：[3,3,2]
示例 4：输入：root = [3,2,4,1] 输出：[7,9,4,10]
分析:
1.这道题居然和 1038 一模一样
class Solution {
private:
int sum = 0;
public:
TreeNode* convertBST(TreeNode* root) {
if (root == nullptr) {
return nullptr;
}
convertBST(root->right);
sum += root->val;
root->val = sum;
convertBST(root->left);
return root;
}
};
转载请注明来源, from goldandrabbit.github.io
