搜索二叉树判断搜索二叉树：对每个节点来说，左边的小于它，右边的大于它。
中顺扫描(左中右)的结果增加的是检索二叉树。
判断以x为头的子树是不是二叉搜索树
左边的树是搜索二叉树还是搜索max
需要右边的树：右边的树要搜索二叉树吗，min
必须递归返回的信息：整树是否为搜索树，整树的max，整树的min
二叉树的递归型：如果可以向左右树请求信息，我会整理我的可能性所需的信息，向左边的树和右边的树请求并收集信息的返回值。
代码：
//二叉搜索树privatestaticbooleanbstprocess (treenode node，int min，int max ) if ) node==null ) return true； if(node.valmin||node.valmax ) { return false； }returnBSTprocess(node.left，min，node.val ) BSTprocess ) node.right，node.val，max； }判断二叉树复盖的最大高度为h，节点数为n，满足N=2^h -1
不使用二叉树递归模型进行时：求出最大高度，求出节点数，看是否满足关系
用二叉树的递归型进行操作，信息载体包含以该节点为开头的二叉树的最大高度和节点数
代码：
//二叉树的privatestaticbooleanisfull (treenode node ) (infoinfo=fullprocess ) node )； //该节点的子树的高度和节点数//计算高度和节点数是否满足公式int nodes=info.nodes的int height=info.height； if(nodes==math.pow(2，height )-1 ) { return true； } return false； } privatestaticinfofullprocess (treenode node ) if ) node==null ) returnnewinfo ) 0，0 )； infoleftinfo=full process (node.left )； inforigtinfo=full process (node.right； int height=math.max (left info.height，rigtInfo.height ) 1； int nodes=left info.nodesrigtinfo.nodes 1； //放入父节点returnnewinfo(nodes，height )； }整体代码：
包树； publicclassisbstandfull { publicstaticclasstreenode { intval=0； TreeNode left=null； TreeNode right=null； publictreenode(intval ) { this.val=val； }//二叉树结构的public static class info { public int nodes； 公共高度； publicinfo(intnodes，int height ) { this.nodes=nodes； this.height=height； }//二叉搜索树privatestaticbooleanbstprocess (treenode node，int min，int max ) ) if ) node==null ) return true； if(node.valmin||node.valmax ) { return false； }returnBSTprocess(node.left，min，node.val ) BSTprocess ) node.right，node.val，max； //二叉树的privatestaticbooleanisfull (treenode node ) (infoinfo=fullprocess ) node )； //计算该节点的子树的高度和节点数//高度和节点数是否满足
公式 int nodes = info.nodes; int height = info.height; if(nodes==Math.pow(2,height)-1){ return true; } return false; } private static Info Fullprocess(TreeNode node) { if(node==null) return new Info(0,0); Info leftInfo = Fullprocess(node.left); Info rigtInfo = Fullprocess(node.right); int height=Math.max(leftInfo.height,rigtInfo.height)+1; int nodes=leftInfo.nodes+rigtInfo.nodes+1;//算上父节点 return new Info(nodes,height); } public static void main(String[] args) { TreeNode node=new TreeNode(3); node.left=new TreeNode(1); node.right=new TreeNode(20); //node.right.left=new TreeNode(15); // node.right.right=new TreeNode(27); boolean b=BSTprocess(node,Integer.MIN_VALUE,Integer.MAX_VALUE); System.out.println(b); //判断满二叉树 boolean bb= isFull(node); System.out.println(bb); }} 判断一个树是不是平衡二叉树平衡二叉树：每一棵子树，左树和右树的高度差不超过1（<=）
需要三个信息：左树是不是平衡树，右树是不是平衡树，左右树的高度差是不是不超过1
代码：
package Tree;public class BalanceTree { public static class TreeNode{ int val; TreeNode left; TreeNode right; public TreeNode(int val) { this.val = val; } } public static class Info{ boolean Balance; int height; public Info(boolean balance, int height) { Balance = balance; this.height = height; } } //判断是不是平衡树 private static boolean isBalance(TreeNode node) { Info info=BalanceProcess(node); return info.Balance; } private static Info BalanceProcess(TreeNode node) { if(node==null) return new Info(true,0); //判断左右子树是不是平衡树 Info leftInfo = BalanceProcess(node.left); Info rightInfo = BalanceProcess(node.right); int height=Math.max(leftInfo.height,rightInfo.height)+1;//加上根节点的层书 //再判断左右子树的高度差是否不超过1 if(Math.abs(leftInfo.height-rightInfo.height)<2){ if(leftInfo.Balance && rightInfo.Balance){ return new Info(true,height); } } return new Info(false,height); } public static void main(String[] args) { TreeNode node=new TreeNode(3); //node.left=new TreeNode(1); node.right=new TreeNode(20); //node.right.left=new TreeNode(15); //node.right.right=new TreeNode(27); //node.right.right.left=new TreeNode(30); //node.right.right.right=new TreeNode(31); boolean b=isBalance(node); System.out.println(b); }} 找最近的公共祖先节点
如果左树上有一个，右树上有一个，那么根节点就是最近的公共祖先。
如果两个结点全在左树上或者全在右树上。
三个信息：最近的公共祖先是否为空（找没有找到），整棵树上是否发现了o1,整棵树上是否发现了o2
当是在两侧分别发现的两个结点，那么根节点就是最近的公共祖先
还要考虑根节点是不是两个节点中的一个。
如果x等于o1（o1），那说明在整棵树上发现了o1（o2）。
在左右子树上只发现了o1，但是在根节点发现了o2，那么公共祖先就是根节点
判断条件：宽度优先遍历，满足两个条件
1、遍历的任何结点不可能有右孩子没有左孩子
2、如果遇到了孩子不全的结点，那么后面的结点必为叶子节点（左右孩子为空）
5是一个转折
如果你之前遇到过不双全的结点，但此时的结点左右孩子不为空（不是叶子节点）。说明该树不是完全二叉树
isMeet一旦改为true，后面的节点一定要是叶子节点