【完全二叉树节点数量】

209 阅读 0 评论 138 点赞

我是靠谱客的博主畅快枫叶，这篇文章主要介绍【完全二叉树节点数量】，现在分享给大家，希望可以做个参考。

完全二叉树的左右子树至少有一个是满二叉树

如果左子树的高度等于右子树高度+1，那么右子树必然是一颗满二叉树
如果左子树的高度等于右子树高度，那么左子树必然是一颗满二叉树
100 28

class Solution {
    public int countNodes(TreeNode root) {
        if(root == null)
        return 0;
        int leftH = getH(root.left);
        int rightH = getH(root.right);
        if(leftH == rightH)
        return (int)Math.pow(2,leftH) + countNodes(root.right);
        else
        return (int)Math.pow(2,rightH) + countNodes(root.left);
    }
    public int getH(TreeNode root){
        int nums = 0;
        while(root != null){
            nums++;
            root = root.left;
        }
        return nums;
    }
}