目录
验证⼆叉搜索树（medium）
题目解析
讲解算法原理
编写代码
⼆叉搜索树中第k⼩的元素（medium）
题目解析
讲解算法原理
编写代码
验证⼆叉搜索树（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给你⼀个⼆叉树的根节点root，判断其是否是⼀个有效的⼆叉搜索树。有效⼆叉搜索树定义如下：
• 节点的左⼦树只包含⼩于当前节点的数。• 节点的右⼦树只包含⼤于当前节点的数。• 所有左⼦树和右⼦树⾃⾝必须也是⼆叉搜索树。⽰例1：
输⼊：root=[2,1,3]输出：true
⽰例2：
输⼊：root=[5,1,4,null,null,3,6]输出：false
解释：根节点的值是5，但是右⼦节点的值是4。
讲解算法原理
解法（利⽤中序遍历）：
后序遍历按照左⼦树、根节点、右⼦树的顺序遍历⼆叉树的所有节点，通常⽤于⼆叉搜索树相关题⽬。
算法思路：
如果⼀棵树是⼆叉搜索树，那么它的中序遍历的结果⼀定是⼀个严格递增的序列。
因此，我们可以初始化⼀个⽆穷⼩的全区变量，⽤来记录中序遍历过程中的前驱结点。那么就可以在中序遍历的过程中，先判断是否和前驱结点构成递增序列，然后修改前驱结点为当前结点，传⼊下⼀层的递归中。
算法流程：
1. 初始化⼀个全局的变量prev，⽤来记录中序遍历过程中的前驱结点的val；
2. 中序遍历的递归函数中：
a. 设置递归出⼝：root==nullptr的时候，返回true；
b. 先递归判断左⼦树是否是⼆叉搜索树，⽤retleft标记；
c. 然后判断当前结点是否满⾜⼆叉搜索树的性质，⽤retcur标记：
▪ 如果当前结点的val⼤于prev，说明满⾜条件，retcur改为true；
▪ 如果当前结点的val⼩于等于prev，说明不满⾜条件，retcur改为false；
d. 最后递归判断右⼦树是否是⼆叉搜索树，⽤retright标记；
3. 只有当retleft、retcur和retright都是true的时候，才返回true。
编写代码
c++算法代码：
/**
* 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 prev = LONG_MIN;
public:
bool isValidBST(TreeNode* root)
{
if(root == nullptr) return true;
bool left = isValidBST(root->left);
// 剪枝
if(left == false) return false;
bool cur = false;
if(root->val > prev)
cur = true;
// 剪枝
if(cur == false) return false;
prev = root->val;
bool right = isValidBST(root->right);
return left && right && cur;
}
};java算法代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution
{
long prev = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root)
{
if(root == null) return true;
boolean left = isValidBST(root.left);
// 剪枝
if(left == false) return false;
boolean cur = false;
if(root.val > prev) cur = true;
if(cur == false) return false;
prev = root.val;
boolean right = isValidBST(root.right);
return left && cur && right;
}
}⼆叉搜索树中第k⼩的元素（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给定⼀个⼆叉搜索树的根节点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
讲解算法原理
解法⼆（中序遍历+计数器剪枝）：算法思路：
上述解法不仅使⽤⼤量额外空间存储数据，并且会将所有的结点都遍历⼀遍。但是，我们可以根据中序遍历的过程，只需扫描前k个结点即可。
因此，我们可以创建⼀个全局的计数器count，将其初始化为k，每遍历⼀个节点就将count--。直到某次递归的时候，count的值等于1，说明此时的结点就是我们要找的结果。
算法流程：
1. 定义⼀个全局的变量count，在主函数中初始化为k的值（不⽤全局也可以，当成参数传⼊递归过程中）；
递归函数的设计：intdfs(TreeNode*root)：
• 返回值为第k个结点；
递归函数流程（中序遍历）：
1. 递归出⼝：空节点直接返回-1，说明没有找到；
2. 去左⼦树上查找结果，记为retleft：
a. 如果retleft==-1，说明没找到，继续执⾏下⾯逻辑；
b. 如果retleft!=-1，说明找到了，直接返回结果，⽆需执⾏下⾯代码（剪枝）；
3. 如果左⼦树没找到，判断当前结点是否符合：
a. 如果符合，直接返回结果
4. 如果当前结点不符合，去右⼦树上寻找结果。
编写代码
c++算法代码：
/**
* 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
{
int count;
int ret;
public:
int kthSmallest(TreeNode* root, int k)
{
count = k;
dfs(root);
return ret;
}
void dfs(TreeNode* root)
{
if(root == nullptr || count == 0) return;
dfs(root->left);
count--;
if(count == 0) ret = root->val;
dfs(root->right);
}
};java算法代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution
{
int count;
int ret;
public int kthSmallest(TreeNode root, int k)
{
count = k;
dfs(root);
return ret;
}
void dfs(TreeNode root)
{
if(root == null || count == 0) return;
dfs(root.left);
count--;
if(count == 0) ret = root.val;
if(count == 0) return;
dfs(root.right);
}
}