目录
700.二叉搜索树的搜索
题目
给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
示例 1:
输入：root = [4,2,7,1,3], val = 2 输出：[2,1,3]
代码（二叉搜索树迭代）
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
while(root != null){
//值相等，直接返回节点
if(root.val == val){
return root;
}
//target小，往左子树走
else if(root.val > val){
root = root.left;
}
//targer大，往右子树走
else if(root.val < val){
root = root.right;
}
}
//最后root走到空，说明没找到
return null;
}
}代码（二叉搜索树递归）
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
//终止条件
if(root == null){
return null;
}
if(root.val == val){
return root;
}
//单层逻辑
if(root.val > val){
return searchBST(root.left,val); //目标小，往左子树走
}
//这里要用else，不然报错没有返回值
else{
return searchBST(root.right,val); //目标大，往右子树走
}
}
}代码（普通二叉树递归）
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
//终止条件
if(root == null || root.val == val){
return root;
}
//单层逻辑(前序遍历)
TreeNode left = searchBST(root.left,val);
TreeNode right = searchBST(root.right,val);
if(left != null){
return left;
}
else{
return right;
}
}
}代码（普通二叉树迭代）
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
Stack<TreeNode> stack = new Stack<>();
if(root == null){
return null;
}
stack.push(root);
while(!stack.isEmpty()){
TreeNode cur = stack.pop();;
if(cur.val == val){
return cur;
}
if(cur.right != null){
stack.push(cur.right);
}
if(cur.left != null){
stack.push(cur.left);
}
}
return null;
}
}98.验证二叉搜索树
题目
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3] 输出：true
代码（中序递归得到中序序列）
class Solution {
public boolean isValidBST(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null){
return true;
}
inOrder(root,list); //获取中序遍历序列list
for(int i=1;i < list.size();i++){
if(list.get(i) <= list.get(i-1)){ //判断list是否递增
return false;
}
}
//list递增，返回true
return true;
}
//中序递归二叉树，list存储中序遍历序列
public void inOrder(TreeNode root,List<Integer> list){
//终止条件
if(root == null){
return;
}
//单层逻辑
inOrder(root.left,list); //递归左子树
list.add(root.val); //处理中间节点
inOrder(root.right,list); //递归右子树
}
}代码（中序迭代得到中序序列）
class Solution {
public boolean isValidBST(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null){
return true;
}
//中序迭代遍历得到中序序列
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()){
//cur非空，一直走到左子树最下
while(cur != null){
stack.push(cur);
cur = cur.left;
}
//cur为空，最左下节点出栈
cur = stack.pop();
list.add(cur.val);
cur = cur.right;
}
for(int i=1;i < list.size();i++){
if(list.get(i) <= list.get(i-1)){ //判断list是否递增
return false;
}
}
//list递增，返回true
return true;
}
}代码（中序递归）
class Solution {
//核心是pre的设计，pre代表中序序列下root的前一个节点
//判断中间节点root时，root必须大于pre的值
TreeNode pre = null; //pre初始化为空，之后就一直指向root的前一个中序节点
public boolean isValidBST(TreeNode root) {
//终止条件
if(root == null){
return true;
}
//单层逻辑
boolean left = isValidBST(root.left); //判断左子树是否满足
//判断中间节点root是否比左子树的都大，pre是左子树最大节点
if(pre != null && root.val <= pre.val){
return false;
}
pre = root; //更新pre，指向中间节点
boolean right = isValidBST(root.right); //判断右子树是否满足
return left && right; //左右子树同时满足
}
}代码（中序迭代）
class Solution {
//核心是pre的设计，pre代表中序序列下root的前一个节点
//判断中间节点root时，root必须大于pre的值
TreeNode pre = null; //pre初始化为空，之后就一直指向root的前一个中序节点
public boolean isValidBST(TreeNode root) {
//终止条件
if(root == null){
return true;
}
//中序迭代
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
TreeNode pre = null; //增加pre，指向root的前一个节点
while(cur != null || !stack.isEmpty()){
//cur非空一直往左子树走
while(cur != null){
stack.push(cur);
cur = cur.left;
}
//cur为空，最左下节点出栈
cur = stack.pop();
if(pre != null && pre.val >= cur.val){
return false;
}
pre = cur;
cur = cur.right; //往右子树走
}
return true;
}
}530.二叉搜索树的最小绝对差
题目
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
示例 1：
输入：root = [4,2,6,1,3] 输出：1
代码（中序递归得到中序序列）
class Solution {
public int getMinimumDifference(TreeNode root) {
List<Integer> list = new ArrayList<>();
inOrder(root,list);
int min = Integer.MAX_VALUE;
for(int i=1;i < list.size();i++){
int abs = list.get(i) - list.get(i-1);
if(abs < min){
min = abs;
}
}
return min;
}
//中序递归得到中序序列list
public void inOrder(TreeNode root,List<Integer> list){
if(root == null){
return;
}
inOrder(root.left,list);
list.add(root.val);
inOrder(root.right,list);
}
}代码（中序迭代得到中序序列）
class Solution {
public int getMinimumDifference(TreeNode root) {
List<Integer> list = new ArrayList<>();
inOrder(root,list);
int min = Integer.MAX_VALUE;
for(int i=1;i < list.size();i++){
int abs = list.get(i) - list.get(i-1);
if(abs < min){
min = abs;
}
}
return min;
}
//中序遍历得到中序序列list
public void inOrder(TreeNode root,List<Integer> list){
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
list.add(cur.val);
cur = cur.right;
}
}
}代码（中序迭代）
class Solution {
public int getMinimumDifference(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode pre = null; //代表cur的前一个中序节点
TreeNode cur = root;
int result = Integer.MAX_VALUE; //初始化最大值
while(cur != null || !stack.isEmpty()){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
//更新最小值
if(pre != null){
int abs = cur.val - pre.val;
if(abs < result){
result = abs;
}
}
pre = cur;
cur = cur.right;
}
return result;
}
}代码（中序递归）
class Solution {
TreeNode pre = null; //pre指向中序序列的前一个节点
int result = Integer.MAX_VALUE; //初始化result
public int getMinimumDifference(TreeNode root) {
//终止条件
if(root == null){
return result;
}
//单层逻辑
result = getMinimumDifference(root.left); //获取左边的最小值
//获取中间节点的最小值
if(pre != null){
int abs = root.val - pre.val;
if(abs < result){
result = abs;
}
}
pre = root;
result = getMinimumDifference(root.right); //获取右边的最小值
return result;
}
}