明天持续二叉树的递归套路。

一、判断是否是满二叉树

满二叉树定义：对于高度为 h 的二叉树，节点数为（2^h – 1）

1、递归套路思路

依据满二叉树的定义能够晓得，咱们每次只须要获取高度、节点数即可。

也就是每次从左子树和右子树中咱们都须要 高度、节点数 两个数据，最初再依据高度和节点数的关系判断是否是满二叉树。所以能够定义如下的 Info 类

/**
 * @author Java 和算法学习：周一
 */
public static class Info {
    public int height;
    public int nodes;

    public Info(int height, int nodes) {
        this.height = height;
        this.nodes = nodes;
    }
}

2、递归套路代码

（1）首先判断为空时好不好设置，此时是好设置的，节点为空时 new Info(0, 0)，即认为空节点高度为 0、节点数为 0。

（2）而后依据列出的所有可能性，编写递归套路的代码，因为要整个造成递归，所以每一步都要返回 Info 类。（无脑拿到左右子树的 Info、拼凑本人的 Info、返回本人的 Info）

/**
 * @author Java 和算法学习：周一
 */
public static Info process(Node x) {if (x == null) {return new Info(0, 0);
    }

    // 获取左右子树的信息
    Info leftInfo = process(x.left);
    Info rightInfo = process(x.right);

    // 拼凑本人的信息
    int height = Math.max(leftInfo.height, rightInfo.height) + 1;
    int nodes = leftInfo.nodes + rightInfo.nodes + 1;

    return new Info(height, nodes);
}

（3）主函数调用递归办法获取后果

/**
 * @author Java 和算法学习：周一
 */
public static boolean isFull(Node head) {if (head == null) {return true;}
    Info process = process(head);
    return (1 << process.height) - 1 == process.nodes;
}

所有代码地址：https://github.com/monday-pro/algorithm-study/blob/master/src/basic/binarytree/IsFullBinaryTree.java

二、求二叉树中最大子搜寻二叉树的节点数

给定一个二叉树，整体可能是、也可能不是搜寻二叉树，然而它的某几个子树是搜寻二叉树，要找到节点数最多的子搜寻二叉树的节点数。

1、递归套路思路

求最大子搜寻二叉树，分为两种可能性，蕴含二叉树头节点，不蕴含二叉树头节点。

（1）不蕴含头节点：需要求左树的最大搜寻二叉树的节点数，需要求右树的最大搜寻二叉树的节点数

（2）蕴含头节点：须要判断左树是不是搜寻二叉树，右树是不是搜寻二叉树，左树的最大值是否小于头节点，右树的最小值是否大于头节点，同时还须要左树和右树的节点数。

也就是每次从左树和右树中咱们都须要 最大搜寻二叉树的节点数、是否搜寻二叉树、max、min、节点数 ，然而还能化简，如果最大搜寻二叉树的节点数和节点数相等就意味着整个子树是搜寻二叉树，所以能够化简为 最大搜寻二叉树的节点数、max、min、节点数。只管咱们最初只返回节点数，然而咱们须要是否搜寻二叉树、max、min 来辅助求解节点数。最初，能够定义如下的 Info 类

/**
 * @author Java 和算法学习：周一
 */
public static class Info {
    // 最大满足搜寻二叉树条件的子树大小
    public int maxSubSize;

    public int max;

    public int min;

    // 整个子树的节点数
    public int allSize;

    public Info(int maxSubSize, int max, int min, int allSize) {
        this.maxSubSize = maxSubSize;
        this.max = max;
        this.min = min;
        this.allSize = allSize;
    }
} 

2、递归套路代码

（1）首先判断为空时好不好设置，此时是不好设置的，节点为空时 max 和 min 不好指定，所以节点为空时间接返回 null，前面递归时再解决这个 null 即可。

（2）而后依据列出的所有可能性，编写递归套路的代码，因为要整个造成递归，所以每一步都要返回 Info 类。（无脑拿到左右子树的 Info、拼凑本人的 Info、返回本人的 Info）

/**
 * @author Java 和算法学习：周一
 */
public static Info process(Node x) {if (x == null) {return null;}

    // 获取左右子树信息
    Info leftInfo = process(x.left);
    Info rightInfo = process(x.right);

    // 拼凑本人的信息
    int max = x.value;
    int min = x.value;
    int allSize = 1;
    if (leftInfo != null) {max = Math.max(leftInfo.max, max);
        min = Math.min(leftInfo.min, min);
        allSize += leftInfo.allSize;
    }
    if ((rightInfo != null)) {max = Math.max(rightInfo.max, max);
        min = Math.min(rightInfo.min, min);
        allSize += rightInfo.allSize;
    }

    // 左树 最大搜寻二叉树大小
    int p1 = -1;
    if (leftInfo != null) {p1 = leftInfo.maxSubSize;}

    // 右树 最大搜寻二叉树大小
    int p2 = -1;
    if (rightInfo != null) {p2 = rightInfo.maxSubSize;}

    // 最大子树蕴含头节点
    int p3 = -1;
    // 左树是否是搜寻二叉树
    boolean leftSearch = leftInfo == null || leftInfo.maxSubSize == leftInfo.allSize;
    // 右树是否是搜寻二叉树
    boolean rightSearch = rightInfo == null || rightInfo.maxSubSize == rightInfo.allSize;
    if (leftSearch && rightSearch) {
        // 左树最大值是否比以后节点值小（空也认为比以后节点小）boolean lessMaxLessX = leftInfo == null || leftInfo.max < x.value;
        // 右树最小值是否比以后节点值大（空也认为比以后节点大）boolean rightMinMoreX = rightInfo == null || rightInfo.min > x.value;

        // 都满足，能力批改 p3 的值
        if (lessMaxLessX && rightMinMoreX) {
            int leftSize = leftInfo == null ? 0 : leftInfo.allSize;
            int rightSize = rightInfo == null ? 0 : rightInfo.allSize;
            p3 = leftSize + rightSize + 1;
        }
    }

    // 最初批改，以后子树最大搜寻二叉子树的大小
    int maxSubSize = Math.max(p1, Math.max(p2, p3));

    return new Info(maxSubSize, max, min, allSize);
}

（3）主函数调用递归办法获取后果

/**
 * @author Java 和算法学习：周一
 */
public static int maxSubSearchBinaryTreeSize(Node head) {if (head == null) {return 0;}
    return process(head).maxSubSize;
}

所有代码地址：https://github.com/monday-pro/algorithm-study/blob/master/src/basic/binarytree/MaxSubSearchBinaryTreeSize.java

三、二叉树递归套路总结

是不是感觉对二叉树的递归套路有点感觉了，是时候总结一下二叉树的递归套路了。

1、假如以 X 节点为头，假如能够向 X 左树和 X 右树要任何信息

2、在上一步的假如下，探讨以 X 为头节点的树，列出失去答案的可能性(最重要)

3、列出所有可能性后，确定到底须要向左树和右树要什么样的信息

4、把左树信息和右树信息求选集，就是任何一棵子树都须要返回的信息 Info

5、递归函数都返回 Info，每一棵子树都这么要求

6、写代码，在代码中思考如何把左树的信息和右树信息整合出整棵树的信息

当看完了前几篇的二叉树递归套路，再看这个总结，是不是信手拈来。