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

https://leetcode-cn.com/problems/count-complete-tree-nodes/

解法一：暴力递归

class Solution:
    def countNodes(self, root: TreeNode) -> int:
        if not root:
            return 0
        return self.countNodes(root.left) + self.countNodes(root.right) + 1

二、利用完全二叉树性质

性质：一棵完全二叉树的两棵子树，至少有一棵是满二叉树（如图） 满二叉树的节点（高为h）可以用公式2^h-1计算。每次找左子树最左节点的深度hl，和右子树最右节点深度hr，若hl==hr，则该树一定是满二叉树，直接返回节点数 若hl != hr，再正常递归

class Solution:
    def countNodes(self, root: TreeNode) -> int:
        l=root
        hl=0
        while l != None:
            l = l.left
            hl+=1
        r=root
        hr=0
        while r != None:
            r = r.right
            hr+=1
        if hl == hr:
            return 2**hl - 1
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)

优化在哪？关键点在于，这两个递归只有一个会真的递归下去，另一个一定会触发 hl == hr 而立即返回，不会递归下去。 综上，算法的递归深度就是树的高度 O(logN)，每次递归所花费的时间就是 while 循环，需要 O(logN)，所以总体的时间复杂度是 O(logN*logN)。