目录
530.二叉搜索树的最小绝对差
题意：
给你一个二叉搜索树的根节点
root，返回 树中任意两不同节点值之间的最小差值 。差值是一个正数，其数值等于两值之差的绝对值。
- 树中节点的数目范围是
[2, 100]0 <= Node.val <= 105
【输入样例】root = [4,2,6,1,3]
【输出样例】1
解题思路：
二叉搜索树的特点，左子树的所有值都比根节点小，右子树的所有值都比根节点大；
要找最小差值，其选择一定为相邻两个元素之差的最小值。
通过遍历树来计算差值，并将结果保存起来，边遍历边比较。
遍历方法使用中序遍历，因为中序遍历出来的结果是有序的。
class Solution {
int ans,pre;//Pre保存前驱节点的值
public int getMinimumDifference(TreeNode root) {
ans = Integer.MAX_VALUE;
pre = -1;//提示中说明节点值的范围是[0,105],所以初始化为-1
midOrder(root);
return ans;
}
void midOrder(TreeNode root){
if(root == null){
return;
}
midOrder(root.left);
if(pre == -1){
pre = root.val;
}else{
ans = Math.min(ans, root.val - pre);
pre = root.val;
}
midOrder(root.right);
}
}时间： 击败了100.00%
内存： 击败了29.78%
230.二叉搜索树中第K小的元素
题意：
给定一个二叉搜索树的根节点
root，和一个整数k，请你设计一个算法查找其中第k个最小元素（从 1 开始计数）。提示：
- 树中的节点数为
n。1 <= k <= n <= 1040 <= Node.val <= 104
【输入样例】root = [3,1,4,null,2], k = 1
【输出样例】1
解题思路：
中序遍历找到第k个数就可以了。
为了避免遍历完所有节点，不使用递归搜索，而是使用迭代搜索，借助栈
class Solution {
public int kthSmallest(TreeNode root, int k) {
Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
while(root != null || !stack.isEmpty()){
while(root != null){
stack.push(root);//先把根存进去，然后先找左子树
root = root.left;//左 根 右，持续进栈根节点，直到找到最左的节点
}
//循环结束条件是root为空，证明上一个root没有左节点，出栈
root = stack.pop();
--k;//遍历到一个数减一次
if(k == 0){
break;
}
root = root.right;//往节点右子树找了
}
return root.val;
}
}时间： 击败了24.31%
内存： 击败了75.46%
98.验证二叉搜索树
题意：
给你一个二叉树的根节点
root，判断其是否是一个有效的二叉搜索树。有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
提示：
- 树中节点数目范围在
[1, 104]内-231 <= Node.val <= 231 - 1
【输入样例】root = [2,1,3]
【输出样例】true
解题思路：
跟上一题一样，借助栈进行中序遍历，用pre保存前一节点的值，如果root.val <=pre，则表示不是二叉搜索树。
class Solution {
public boolean isValidBST(TreeNode root) {
double pre = -Double.MAX_VALUE;;
Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
while(root != null || !stack.isEmpty()){
while(root != null){
stack.push(root);
root = root.left;
}
root = stack.pop();
if(root.val <= pre){//=也不符合二叉搜索树的要求
return false;//不满足
}
pre = root.val;
root = root.right;
}
return true;
}
}时间： 击败了18.62%
内存： 击败了49.12%
