MENU

LeetCode222. 完全二叉树的节点个数

August 9, 2018 • Read: 3506 • LeetCode阅读设置

题目链接:LeetCode222

题解

常规思路,遍历整棵树,时间复杂度O(N),但是有一种时间复杂度小于O(N)的做法

首先遍历头结点右子树的最左边界,如果最左边界不为空,说明头结点的左子树是满二叉树,利用满二叉树的性质,结点个数就为$2^h-1$,再加上头结点,所以结果就是$2^h$,这个时间复杂度是O(logN)的,然后再递归遍历右子树求出有多少结点即可

如果最左边界为空,说明头结点的右子树是一棵高度为$h-1$的满二叉树,那么右子树加上头结点的总结点个数就为$2^{h-1}$,然后再递归遍历头节点的左子树即可

代码
class Solution {
    int h;
    public int countNodes(TreeNode root) {
        h = mostLeftLevel(root,1);
        if(root == null) 
            return 0;
        return bs(root,1);
    }
    public int bs(TreeNode node,int level) {
        if(level == h) 
            return 1;
        if(mostLeftLevel(node.right,level + 1) == h)
            return (1 << (h - level)) + bs(node.right,level + 1);
        return (1 << (h - level - 1)) + bs(node.left,level + 1);
    }
    public int mostLeftLevel(TreeNode node,int level) {
        while(node != null) {
            level++;
            node = node.left;
        }
        return level - 1;
    }
}
Last Modified: May 12, 2021
Archives Tip
QR Code for this page
Tipping QR Code