二叉树一般的递归套路
1.假设你自己需要哪些子树的哪些返回信息，自己构造一个类来存储这些信息。例如判断一棵树是否为平衡二叉树，那么假设自己处于当前节点的位置，需要左右子树提供的信息是：1.子树自身是否为平衡二叉树(布尔类型的变量);2.子树的高度（类型是整型），需要比较左右子树的高度差值是多少。构造含有这两种类型的返回值类即可。就可以在父类中进行利用。
递归的关键就是将之后的递归信息看作信息直接获得，不能去模拟之后的函数如何调用，否则越模拟越乱。
//构造子树返回的信息对象
public static class ReturnType{
//返回信息
public int height ;
public boolean isbalance;
//构造函数
public ReturnType(int height,boolean isbalance){
this.height = height;
this.isbalance =isbalance;
}
}
public static ReturnType getBanlanceTree(TreeNode root){
if(root==null){
return new ReturnType(0,true);
}
ReturnType leftdata = getBanlanceTree(root.left);
ReturnType rightdata = getBanlanceTree(root.right);
int height = Math.max(leftdata.height,rightdata.height)+1;
boolean isbalance = leftdata.isbalance && rightdata.isbalance
&& (Math.abs(leftdata.height-rightdata.height)<2);
return new ReturnType(height,isbalance);
}
2.判断是不是二叉搜索树。
思路：因为需要判断一颗树是否是搜素二叉树，
需要判断的信息有 :
- 左子树是否是搜索二叉树；右子树是否是搜索二叉树；
- 左子树的最大值，以及右子树的最小值。
- 因为递归需要统一形式，所以返回三个值，是否是搜索树，以及最大值，最小值
public class IsSearchTree {
public static void main(String[] args) {
Integer[] root = {2147483647};
TreeNode node=CreateTree(root,0);
System.out.println(isSearchTree(node).isSearch);
}
public static ReturnType isSearchTree(TreeNode root){
if(root==null){
return new ReturnType(Long.MIN_VALUE,Long.MAX_VALUE,true);
}
ReturnType leftdata = isSearchTree(root.left);
ReturnType rightdata = isSearchTree(root.right);
long max = Math.max(Math.max(leftdata.maxValue,rightdata.maxValue),root.val);
long min = Math.min(Math.min(leftdata.minValue,rightdata.minValue),root.val);
return new ReturnType(max,min,leftdata.isSearch && rightdata.isSearch && (root.val>leftdata.maxValue) &&(root.val<rightdata.minValue));
}
public static class ReturnType{
public long maxValue;
public long minValue;
public boolean isSearch;
public ReturnType(long maxValue,long minValue,boolean isSearch){
this.maxValue = maxValue;
this.minValue = minValue;
this.isSearch = isSearch;
}
}
}
3.判断是不是满二叉树。需要子树提供的是高度和节点数目，在当前层判断高度和节点的个数即可。
res.nodeCount == ((1<<res.height)-1); //这样计算次幂
public static boolean isFull(TreeNode node){
if(node==null) return true;
ReturnType res = isFullHelper(node);
return res.nodeCount == (int) ((Math.pow(2,res.height))-1);
}
public static ReturnType isFullHelper(TreeNode node){
if(node==null) return new ReturnType(0,0);
ReturnType leftdata = isFullHelper(node.left);
ReturnType rightdata = isFullHelper(node.right);
return new ReturnType(Math.max(leftdata.height,rightdata.height)+1,leftdata.nodeCount+rightdata.nodeCount+1);
}
//判断满二叉树需要子树提供高度和节点数的信息
public static class ReturnType{
public int height;
public int nodeCount;
public ReturnType(int height,int nodeCount){
this.height=height;
this.nodeCount = nodeCount;
}
}
