求完全二叉树其节点的个数

已知一棵完全二叉树, 求其节点的个数

要求: 时间复杂度低于O(N), N为这棵树的节点个数

public int countNodes(TreeNode root) {
        if (root == null) return 0;
        return bs(root,1,heightOfCompleteTree(root,1));
    }

    public static int heightOfCompleteTree(TreeNode root,int level){
        while (root != null){
            root = root.left;
            level++;
        }
        return level-1;
    }

    public static int bs(TreeNode root,int level, int height){
        if (level == height ) return 1;
        if (heightOfCompleteTree(root.right,level+1) == height){
            return (1<<(height - level)) + bs(root.right,level+1,height);
        }else {
            return (1<<(height - level - 1)) + bs(root.left,level+1,height);
        }
    }

注意:>> 与 <<的用法:

System.out.println( 1 << 2+2 );   输出结果为16
>> 与 << 的运算优先级比 + - 要低

这里的主要两个逻辑为:

public static int heightOfCompleteTree(TreeNode root,int level){
        while (root != null){
            root = root.left;
            level++;
        }
        return level-1;
    }
    
这个函数的意思是:以level层的节点root计算这个树的最大的深度。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券