二叉搜寻树
广告：最近 github 上新开了一个仓库 May-Nodes，包含但不限于之前面试遇到的相干数据库, 计算机操作系统,Java 基础知识，计算机网络以及 LeetCode 等算法题解等常识。届时也会整顿学习应用的 PDF 文档与资源。有须要的小伙伴 能够点个关注和
star。在继续更新中，总会遇到你想要的。
前言
首先明确二叉搜寻树系列的特殊性：二叉搜寻树(Binary Search Tree 简称为 BST)，对于其的特点是任意节点的值都要大等于左子树所有节点的值，且要小于等于左边子树的所有节点的值。其左右子树的个性也就奠定了其在操作过程中就是有迹可循的。
两个根底的框架局部
首先是二叉搜寻树的总的设计理念：
void BinarySearch(TreeNode root){if(root ...)
// 进行系列的操作；BinarySearch(root.left);
BinarySearch(root.right);
}当然这个设计理念的思维就是说，咱们只管进行具体的递归操作，具体的操作咱们就能够参见是先序，中序还是后续而后做具体的操作，举个栗子：对于 700- 二叉搜寻树的搜寻，咱们只管进行左右子数的循环，其余的交给 root 去解决：
public TreeNode searchBST(TreeNode root, int val) {if(root == null)
return root;
if(root.val == val) return root;
else if(root.val> val) return searchBST(root.left,val);
else return searchBST(root.right,val);
}其上就是对二叉树只进行查问的操作，然而不波及到任何的批改操作，只须要简略判断即可，然而对于还有一部分的二叉搜寻树而言，咱们须要对左右子数进行简略的解决和判断：
举个栗子：判断一棵二叉树是否是对称的对称的二叉树，就须要对节点值进行判断解决（以下的思维也是在很多中央都可能用到的思维）
- 对于这类的题目来说，能够将逻辑块分成一个具体的函数，因为有的时候，咱们的逻辑块可能并没有具体的返回值，也有的时候，想要的最初的返回值喝逻辑块在运行中的返回值不同。
- 对于这类的题目，个别都是判断是否相等，判断两颗树是否是相等的等，都是须要对树中的值进行对应的判断解决。
public boolean isSymmetric(TreeNode pRoot) {if(pRoot==null)
return true;
return issys(pRoot.left,pRoot.right);
}
private boolean issys(TreeNode l,TreeNode r){if(l==null && r==null){
return true;
// 次要是判断对于两颗树来说对应的节点是否都不存在，都不存在时候 示意不必比拟，就能够返回正常值。}
if(l==null ||r==null){
return false;
// 示意本该对应的节点上，一个是 null 一个却不是 null 时候，返回一个谬误的值。}
if(l.val!=r.val)
{
return false;
// 留神 这里该判断两者不相等 返回一个谬误值，而不是两者相等返回正确值
// 因为 若是呈现左右子数雷同时候 以后是正确的 然而若是咱们间接返回正确值
// 上面的状况 就有可能没方法失去正确的判断。}
return issys(l.left,r.right)&& issys(l.right,r.left);
}具体示例
简略实现版：
以上就是具体的框架局部，一个实用于对值具体查找的判断，一个应用于节点的等值判断。
二叉搜寻树的最近公共先人
具体的题目能够去查看原题局部，这里咱们进行剖析，首先对于这个题目来说，只是他一棵树，而后所有的操作也都是在本身进行判断，所以咱们就能够排除第二种的 判断节点是否存在问题 ，就是应用到第一种的对各自节点进行判断： 判断左右方向 ：咱们要深析二叉搜寻树的特点，让咱们查找的是最近的根节点，就是说要么就是两者为左右节点，根节点不再两者之间，要么就是两者之间有一个就是独特的根节点。上面思考如何进入到左子树：就是给定的两个节点的值都比根节点要小，示意在右边，同理，给定的值都比以后的根要大，岂不就是说，以后的根节点太小了？如此咱们就找到了判断进入左右的办法，其余的就交给root 就好。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root.val< p.val && root.val <q.val)
return lowestCommonAncestor(root.right,p,q);
else if(root.val > p.val && root.val > q.val)
return lowestCommonAncestor(root.left,p,q);
return root;
}深度版
对于二叉树系列的深度版本而言，次要思维还是根底的进入到左右子树的循环，然而不同的是，之前咱们进入到左右子树循环中，只是图一个遍历的值，当初咱们须要在进行在进行遍历时候获取到一个深度值。
对于这部分的模板是咱们在获取左右值的同时对左右节点的最大值进行一个计算与保留：
public int temp(TreeNode root){if(root == null)
return 0 ;// 示意在不满足的状况下的退出
int left =temp(root.left);
int right = temp(root.right);
return 1+ Math.max(left,right);// 获取到左右方最大值。}二叉树的深度
获取到最大深度
如题目所示，在进行最根底遍历的同时对左右节点进行取最大值（示意取左右节点最大值）。
public int maxDepth(TreeNode root) {return temp(root);
}
public int temp(TreeNode root){if(root == null)
return 0 ;
int left =temp(root.left);
int right = temp(root.right);
return 1+ Math.max(left,right);
}判断是否均衡二叉树
判断是否是均衡二叉树
这个题目原型就是咱们的二叉树的深度的变形解决，还是要进行左右节点的深度的计算，大体的模板是雷同的，为题目进行简略的变形即可。
class Solution {
boolean temp = false;
public boolean isBalanced(TreeNode root) {isbalance(root);
return !temp;
}
public int isbalance(TreeNode root){if(root == null)
return 0;
int left = isba(root.left);
int right = isba(root.right);
if(Math.max(left,right)-Math.min(left,right)>1){
temp = true;
// 这里咱们就不可能失常的进行值返回 因为咱们在计算的时候，应用到的是 int 类型进行深度的 计算 然而在最初进行值的判断时候 须要的是 boolean 类型 所以 这里设置一个标记位。}
return 1 +Math.max(left,right);
}
}二叉树的直径
二叉树的直径
对于这个变形，次要的思维逻辑还是最开始的一套，次要是对于直径而言，须要对左右子树进行相加，示意的是所有的直径信息，而后在遍历的过程中获得较大值。
class Solution {
int ans;
public int diameterOfBinaryTree(TreeNode root) {
ans=0;
depth(root);
return ans;
}
public int depth(TreeNode root){if(root==null)
return 0;
int l=depth(root.left);
int r=depth(root.right);
ans=Math.max(ans,l+r);
return Math.max(l,r)+1;
}
}中序遍历版
对于寻求中序遍历系列而言，次要是利用咱们最后的中序遍历的模板系列。也是咱们树遍历中的三大遍历模板，对于这部分的题目次要就是利用中序的个性，对两头的代码块进行系列操作
public void temp(TreeNode root){temp(root.left);
... // 进行系列的操作
temp(root.right);
}验证二叉
验证是否为二叉搜寻树
利用中序遍历的思维进行左右的判断。
class Solution {
long pre=Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {if(root==null)
return true;
if(!isValidBST(root.left))
return false;
if(root.val<=pre)
return false;
pre=root.val;
if(!isValidBST(root.right))
return false;
return true;
}
}间隔最小值
二叉搜寻中两两之间差最小值，利用到中序遍历中的 pre 指针示意以后 root 的前驱指针, 两者之间进行判断即可。
class Solution {
TreeNode pre = null;
int temp = Integer.MAX_VALUE;
public int minDiffInBST(TreeNode root) {minvalue(root);
return temp;
}
public void minvalue(TreeNode root){if(root== null)
return;
minvalue(root.left);
if(pre!=null)
{temp =Math.min(temp,root.val-pre.val);
}
pre = root;
minvalue(root.right);
}
}复原二叉搜寻树：
复原二叉搜寻
根底的思维理念，须要留神的是对于这样的一个示例来说 6 345 2来说对于依照咱们根底的替换理念 6 和 3 进行替换，然而走到前面会发现 6 和 2 也要进行替换, 所以要先对前一个值（6）进行判空，判断是否还须要对其的值进行更改。
class Solution {
TreeNode pre,p,q;
public void recoverTree(TreeNode root) {
pre = p = q = null;
getResult(root);
int temp = p.val;
p.val = q.val;
q.val = temp;
}
public void getResult(TreeNode root){if(root == null)
return ;
getResult(root.left);
if(pre!= null && pre.val > root.val){if(p==null){
p = pre;
q = root;
}
else
q = root;
}
pre= root;
getResult(root.right);
}
}门路和
题干
输出一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输出整数的所有门路。门路定义为从树的根结点开始往下始终到叶结点所通过的结点造成一条门路。(留神: 在返回值的 list 中，数组长度大的数组靠前)
思路
- 首先第一步而言，咱们应该明确对于树的操作来言时候，遍历些许都是应用到栈与队列较多，对于树的查问，波及到左右不定变动个别都是递归。
- 而后对于递归而言要判断咱们如何以及何时将正确的门路退出到咱们的后果集中。因为题目中说到，打印的是门路，而门路又是从根节点到叶结点 – 即对于一个节点来说左右子树都为空的状况下就是叶子节点咱们就能够对其进行一个根底的判断。
- 输入的是
ArrayList<ArrayList<Integer>>类型，就须要咱们对于每一个的后果集进行退出，而后对于外部的ArrayList<Integer>进行生成一个新的，个别对于输入后果是ArrayList<ArrayList<Integer>>时候咱们能够这样进行操作。
ArrayList<ArrayList<Integer>> array=new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> list=new ArrayList<Integer>();
list.add(XX);
array.add(list);
list=new ArrayList<Integer>();- 而后胜利之后，例如咱们曾经晓得了一条门路，在增加实现当前，要删除刚刚增加进来的，因为还要进行下一个结点的摸索（后序在呈现此类问题时候会持续深刻的解说）
- 而后就是左右递归摸索即可。
代码
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {this.val = val;}
// [[10,5,7],[10,12]]
}
*/
import java.util.ArrayList;
public class Solution {public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {ArrayList<ArrayList<Integer>> array=new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> list=new ArrayList<Integer>();
if(root==null || target==0)
return array;
sum(root,target,array,list,0);
return array;
}
private void sum(TreeNode t,int target,ArrayList<ArrayList<Integer>> array,ArrayList<Integer> list,int sum){if(t==null || target==0)
return ;
sum=sum+t.val;
if(t.left==null&& t.right==null)
{if(sum==target){list.add(t.val);
array.add(new ArrayList<Integer>(list));
list.remove(list.size()-1);
}
return;
}
list.add(t.val);
sum(t.left,target,array,list,sum);
sum(t.right,target,array,list,sum);
// 这个 remove 会在当下面的两个都遍历实现当前 程序执行下来。list.remove(list.size()-1);
}
}记录
在实现剑指 Offer 之后，还刷到了牛客上 LeetCode 经典题目其中有两个题目感觉和门路问题相识，这里也放进去一起解说一下
path-sum
** 给定一个二叉树和一个值 sum，判断是否有从根节点到叶子节点的节点值之和等于 sum 的门路，
例如：
给出如下的二叉树，sum=22。**
5
4 8
11 13 4
7 2 5 1思路
- 对于这个题目而言同样是根节点到叶子节点，所以还是判断对于左右节点都为空时示意叶子节点，进行门路值的判断
- 而后传参时候进行相减传参能够不必额定定义变量进行值存取，缩小了工作量。
- 因为没有进行值的存取，所以不存在下面的对 remove 操作。
代码
public class Solution {public boolean hasPathSum(TreeNode root, int sum) {if(root==null) return false;
if(root.left==null && root.right==null){if(sum-root.val==0)
return true;
else return false;
}
return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val);
}
}path-sum-II
就是下面的剑指 Offer 二十四
binay-tree-maximum-path-sum
** 给定一个二叉树，请计算节点值之和最大的门路的节点值之和是多少。
这个门路的开始节点和完结节点能够是二叉树中的任意节点
例如：
给出以下的二叉树，**
1
2 3思路
- 本题的难点在于咱们开始的节点是任意的节点，同时题目中隐约的示意是可能会呈现有负值就有点类始于给定你一个数组，其中有正有负，让你判断间断和的最大值，就须要咱们对进行相加的值进行一个与 0 比的操作，判断咱们以后的序列值是否退出咱们想得到后果的序列，就是说咱们最初想得到的最大值是否包含咱们此时遍历到的值。
- 同样是递归进行操作，须要与零值进行比拟，若是大于零就退出到咱们想要的后果中，而后维持一个全局的变量。
- 返回值是判断以以后节点为根的节点的左右子树和是否大于零，若是示意胜利则加上以后的值，否则进行摈弃间接返回以后值，对之前就算较大值是小于零进行摈弃。
代码
public class Solution {
int max_m=Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {getMax(root);
return max_m;
}
private int getMax(TreeNode root){if(root==null)
return 0;
int sum=root.val;
int left=getMax(root.left);
int right=getMax(root.right);
if(left>0){sum+=left;}
if(right>0){sum+=right;}
max_m=Math.max(max_m,sum);
return Math.max(left,right)>0?root.val+Math.max(left,right): root.val;
}
}