package com.jiucaiyuan.net.algrithm.tree;



/**

 * <pre>

 * 【问题】判断一棵树是满二叉树(Full Binary Tree)

 * 【概念】满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。

 *      也就是说，如果一个二叉树的深度为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

 *      (一棵满二叉树的每一个结点要么是叶子结点，要么它有两个子结点，但是反过来不成立，

 *      因为完全二叉树也满足这个要求，但不是满二叉树)

 * 【思路】获得二叉树的深度k及节点个数，然后判断节点个数是否等于(2^k) -1

 * </pre>

 *

 * @Author jiucaiyuan  2022/4/10 17:00

 * @mail services@jiucaiyuan.net

 */



public class IsFullBinaryTree {

    /**

     * 递归套路求解

     *

     * @param root

     */

    public static boolean isFullBinaryTree(Node root) {

        if (root == null) {

            return true;

        }

        Info rootInfo = f(root);

        return rootInfo.nodes == ((1 << rootInfo.height) - 1);

    }



    /**

     * 从左子树获取信息+右子树获取信息，加工出当前子树的信息

     * @param x

     * @return 返回以x为跟的树高度和节点个数

     */

    public static Info f(Node x) {

        if (x == null) {

            return new Info(0, 0);

        }

        Info leftInfo = f(x.left);

        Info rightInfo = f(x.right);

        int height = Math.max(leftInfo.height, rightInfo.height) + 1;

        int nodes = leftInfo.nodes + rightInfo.nodes + 1;

        return new Info(height, nodes);

    }



    static class Info {

        int height;

        int nodes;



        public Info(int h, int n) {

            height = h;

            nodes = n;

        }

    }

}