2022-03-09

二叉树一般的递归套路

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;
        }
    }