leetcode二叉搜索树部分笔记

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

1. 二叉搜索树的最小绝对差

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

解题思路： 二叉搜索树，大小是 左 根 右。
首先确定边界条件： 当root == null时，直接返回。
其次每次递归逻辑：需要从小到大开始，首先去找二叉搜索树的最小值，也就是最左边的节点，找到后，判断pre是否为-1，如果是-1，则仅记录当前节点的值即可。如果不是-1，则说明当前节点比pre大，需要计算两者差值，然后pre更新为当前节点。
最后再去递归右子树节点。

class Solution {int pre;int ans;public int getMinimumDifference(TreeNode root) {ans = Integer.MAX_VALUE;pre = -1;dfs(root);return ans;}public void dfs(TreeNode root) {if (root == null) {return;}dfs(root.left);if (pre == -1) {pre = root.val;} else {ans = Math.min(ans, root.val - pre);pre = root.val;}dfs(root.right);}
}

2. 二叉搜索树中第 K 小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。

解题思路： 中序遍历，然后存入list集合中，然后用list.get（k-1)即可。

class Solution {List<Integer> list = new ArrayList<>();public int kthSmallest(TreeNode root, int k) {dfs(root);return list.get(k-1);}public void dfs(TreeNode root){if(root == null){return;}dfs(root.left);list.add(root.val);dfs(root.right);}
}

3. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

节点的左
子树
只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

解题思路： 中序遍历，判断左子树、根节点、右子树的值是否能遵循二叉搜索树，如果不遵循则让statue等于1，然后返回fasle。

class Solution {Long pre;int state;public boolean isValidBST(TreeNode root) {pre = Long.MIN_VALUE;state = 0;dfs(root);if(state == 1){return false;}return true;}public void dfs(TreeNode root){if(root == null){return;}dfs(root.left);if(pre == Long.MIN_VALUE){pre = (long)root.val;}else{if(pre >= root.val){state = 1;}pre = (long)root.val;}dfs(root.right);}
}