（代码如有错误，烦请各位指正）
1.判断一棵二叉树是否是搜索二叉树搜索二叉树（Binary Search Tree）：按照中序遍历输出的值是严格递增的。
（1）使用之前的中序遍历实现
//使用中序遍历判断是不是二叉树：把中序遍历的输出变成比较即可
static int preValue=Integer.MIN_VALUE;
public static boolean isBinarySearchTree(Tree head){
if(head==null){
return true;
}
boolean left=isBinarySearchTree(head.left);
if(!left){
return false;
}//判断左树是否是搜索二叉树
if(head.value<=preValue){
return false;
}else{
preValue= head.value;
}//判断前一个节点是否小于当前节点，不小直接返回false，满足条件则更新当前值
return isBinarySearchTree(head.right);
}
（2）使用二叉树的固定套路实现
满足搜索二叉树需要满足的条件：左树和右树均是搜索二叉树，左树的最大值比我小，右数的最小值比我大
需要左树提供的条件：左树是否是搜索二叉树，左树的最大值
需要右树提供的条件：右树是否是搜索二叉树，右树的最小值
（为了方便递归，左树和右树都提供最大值和最小值）
//2.使用二叉树的递归套路
//自定义一个输出类
static class BSTReturn{
boolean isBST;
int max;
int min;
public BSTReturn(boolean isBST,int max,int min){
this.isBST=isBST;
this.max=max;
this.min=min;
}
}
//返回当前部分是否是搜索二叉树、最大值和最小值
public static BSTReturn processBST(Tree head){
if(head==null){
return null;
}
BSTReturn left=processBST(head.left);
BSTReturn right=processBST(head.right);
Boolean isBST=true;
int max=head.value;
int min=head.value;
//找到最大值和最小值
if(left!=null){
min=Math.min(min,left.min);
max=Math.max(max,left.max);
}
if(right!=null){
min=Math.min(min,right.min);
max=Math.max(max, right.max);
}
//判断是否是搜索二叉树
if(left!=null && (!left.isBST || left.max >= head.value)){
isBST=false;
}
if(right!=null && (!right.isBST || right.min<=head.value)){
isBST=false;
}
return new BSTReturn(isBST,max,min);
}
//判断结果
public static boolean isBinarySearchTree2(Tree head){
if(head==null){
return true;
}
return processBST(head).isBST;
}
2.判断一棵树是否是完全二叉树
完全二叉树：要不是满，最后一层一定是满或者从左往右依次变满。
使用宽度遍历：当前节点有右无左，直接返回false；只要出现一个节点是叶子节点或者只有左孩子，那么接下来每一个节点都必须是叶节点。
//判断是否是完全二叉树
public static Boolean isCompleteBinaryTree(Tree head){
if(head==null){
return true;
}
Queue queue=new LinkedList<>();
Boolean label=false;
queue.add(head);
while(!queue.isEmpty()){
Tree cur=queue.poll();
if(
(cur.left==null && cur.right!=null)//有右无左
||
(label && (cur.left!=null || cur.right !=null))//已经出现了label=true的节点，但接下来的节点还有左或者右
){
return false;
}
if(cur.left!=null){
queue.add(cur.left);
}
if(cur.right!=null){
queue.add(cur.right);
}
//出现第一个叶节点或者只有左孩子的节点
if(cur.left==null || cur.right==null){
label=true;
}
}
return true;
}
3.判断一棵树是否是满二叉树
满二叉树（full binary tree）：深度d和节点个数n满足：n=2d-1
使用递归套路来解题
满二叉树需要满足的条件：满足n=2d-1的条件
需要左树提供的信息：深度，节点个数
需要右树提供的信息：深度，节点个数
//3.判断是否是满二叉树
static class FBTReturn{
int height;
int nodeNum;
public FBTReturn(int height,int nodeNum){
this.height=height;
this.nodeNum=nodeNum;
}
}
public static FBTReturn FBTProcess(Tree head){
if(head==null){
return new FBTReturn(0,0);
}
FBTReturn left=FBTProcess(head.left);
FBTReturn right=FBTProcess(head.right);
int height=Math.max(left.height, right.height)+1;
int nodeNum= left.nodeNum+right.nodeNum+1;
return new FBTReturn(height,nodeNum);
}
public static Boolean isFullBinaryTree(Tree head){
if(head==null){
return true;
}
int height=FBTProcess(head).height;
int nodeNum=FBTProcess(head).nodeNum;
if(nodeNum!=2*height-1){
return false;
}
return true;
}
4.判断一棵树是否是平衡二叉树
平衡二叉树（Self-balancing Binary Search Tree，AVL树）：其左子树和右子树均为平衡二叉树，且左子树和右子树的高度差的绝对值不超过1
使用二叉树套路解题：
是AVL数需要满足的条件：左右子树均是AVL树，且高度差不超过1
需要左树提供的信息：是否是AVL树，高度
需要右树提供的信息：是否是AVL树，高度
//5.判断是否是AVL树
static class AVLReturn{
Boolean isAVL;
int height;
public AVLReturn(Boolean isAVL,int height){
this.isAVL=isAVL;
this.height=height;
}
}
public static AVLReturn AVLProcess(Tree head){
if(head==null){
return new AVLReturn(true,0);
}
AVLReturn left=AVLProcess(head.left);
AVLReturn right=AVLProcess(head.right);
int height=Math.max(left.height, right.height)+1;
Boolean isAVL;
if(left.isAVL && right.isAVL && Math.abs(left.height-right.height)<2){
isAVL=true;
}else{
isAVL=false;
}
return new AVLReturn(isAVL,height);
}
public static Boolean isAVL(Tree head){
return AVLProcess(head).isAVL;
}
5.给定两个二叉树的节点node1和node2，找到他们的最低公共祖先节点
（1）使用哈希表存储每一个节点的父节点；把node1的父节点存到一个列表里，遍历node2的父节点，直到列表里也有该父节点
//6.最低公共祖先节点
//(1)使用哈希表
public static Tree lowCommentNode(Tree head,Tree node1,Tree node2){
if(head==null || node1==null || node2==null){
return null;
}
//找到所有节点的父节点并一一对应
HashMap hashmap=new HashMap<>();
hashmap.put(head,head);//根节点的父节点是他自己
findFatherMap(head,hashmap);
//存储node1本身以及它的祖先节点
HashSet hashset=new HashSet<>();
Tree cur=node1;
while(hashmap.get(cur)!=cur){
hashset.add(cur);//自己也要存
cur=hashmap.get(cur);
}
hashset.add(head);//根节点也要存
cur=node2;
while(hashmap.get(cur)!=cur){
if(hashset.contains(cur)){
return cur;
}else{
cur=hashmap.get(cur);
}
}
return null;
}
public static void findFatherMap(Tree head, HashMap hashmap){
if(head==null){
return;
}
hashmap.put(head.left,head);
hashmap.put(head.right,head);
findFatherMap(head.left,hashmap);
findFatherMap(head.right,hashmap);
}
（2）
//(2)
public static Tree findLCN(Tree head,Tree node1,Tree node2){
if(head==null || head==node1 || head==node2){
return head;
}
Tree left=findLCN(head.left,node1,node2);
Tree right=findLCN(head.right,node1,node2);
if(left!=null && left!=null){
return head;
}
return left!=null ? left:right;
}
6.在二叉树中找一个节点的后继节点
中序遍历循序该节点的后一个节点叫做该节点的后继节点
该节点有右树：则为该右树上的最左节点；无右树：在上找节点是父节点的左孩子，则该父节点即为所求
//7.找后继节点
public static Tree getSuccsseorNode(Tree node){
if(node==null){
return null;
}
if(node.right!=null){
return getMostLeftNode(node.right);
}else{
Tree parent =node.parent;
while(parent!=null && parent.left!=null){
node=parent;
parent=node.parent;
}
return parent;
}
}
public static Tree getMostLeftNode(Tree node){
if(node==null){
return null;
}
while(node.left!=null){
node=node.left;
}
return null;
}
