算法-二叉树-判断满二叉树

2022-4-10 diaba 笔试题 

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

« 算法-二叉树-最低公共祖先 | 算法-二叉树-判断完全二叉树»

发表评论：

Powered by emlog 京ICP备15045175号-1 Copyright © 2022