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

发表于 | 分类于
做完后感觉对递归又多了一些理解

用时：80min

拿到题的第一个反应当然是DFS解决….

但是这是一个完全二叉树，怎么说也应该把完全二叉树的性质用上才行

可以考察二叉树的左右子树深度

如果左深度 大于 右 ， 说明右边已经满了，满了的个数是 2 的 n 次方 - 1，加上root 是 2 的 n次方，继续递归左边

如果右深度大于左， 说明左边满了，同样，继续递归右边

至于怎么求二叉树的深度，可以从下往上递归

1
2
3
4
var count = function(root) {
        if (root === null) return 0
        return Math.max(count(root.left),count(root.right)) + 1
}

那么总体的代码就是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var countNodes = function(root) {
    if (!root) {
        return 0
    }
    var count = function(root) {
        if (root === null) return 0
        return Math.max(count(root.left),count(root.right)) + 1
    }
    var leftLevel = count(root.left)
    var rightLevel = count(root.right)
    if (leftLevel === rightLevel) {
        return Math.pow(2,leftLevel) + countNodes(root.right)
    } else {
        return Math.pow(2,rightLevel ) + countNodes(root.left)
    }
};