力扣 222. 完全二叉树的节点个数

最近开始刷力扣,将每日做题心得都会发布在这上面,以便日后查看。

起初看到这个题,忘记了完全二叉树的概念是什么,于是回顾一下。

这里参考了以下链接

满二叉树、完全二叉树、平衡二叉树、最优二叉树

时间复杂度:O(logn * logn)

空间复杂度:O(1)

class Solution {
    public int countNodes(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftDepth = getDepth(root.left);
        int rightDepth = getDepth(root.right);
        if(leftDepth == rightDepth){
            //左子树为满树,递归右子树
            return countNodes(root.right) + (1 << leftDepth);
        }else{
            //右子树为满树,递归左子树
            return countNodes(root.left) + (1 << rightDepth);
        }


    }

    //得到树的深度
    public int getDepth(TreeNode node){
        TreeNode root = node;
        int depth = 0;
        while(root != null){
            depth++;
            root = root.left;
        }
        return depth;
    }

}

上一篇:[正则] test结果交替出现


下一篇:从零开始学Go之接口(一):接口