M-NR-222. Count Complete Tree Nodes

'''
    暴力秒了, 简单的递归(bfs也能秒(bfs的空间复杂度要到O(n)了)... 但是递归最简单).
    
    秒完思考一下为啥这题没有用到什么需要额外保存的变量, 因为我们唯一需要保留的就是当前节点数量,
    而节点数量在遍历的过程中不需要额外的逻辑去进行取舍判断, 所以我们只需要通过递归来传递这个
    变量,并进行简单的递增即可.
    
    然后思考貌似没用到complete bt的性质, 进阶思考.
    
    Time: O(n)
    Space: O(logN)->因为是complete, 所以也balanced, 所以说O(h)=O(logN)
'''
# 1 不带helper
class Solution:
    def countNodes(self, root: TreeNode) -> int:
        if not root:
            return 0
        return self.countNodes(root.left) + self.countNodes(root.right)+1
        
# 2 带helper
class Solution:
    def countNodes(self, root: TreeNode) -> int:
        def helper(root, num):
            return helper(root.left, num) + helper(root.right, num) + 1 if root else 0
        return helper(root,0)
        
'''
    瞄了一眼solution, 看了眼复杂度, 没仔细看, 自己思考了一下, 这样的一个CBT的
    节点数量=2**depth-1+最后一层节点数
    
    而最后一层节点数=2**height-树中叶子的空儿子数
    
    所以思路应该是, 先求高度(深度, depth), 再找有多少个空儿子, 就能计算了.
    
    求depth: 一直找左儿子,直到空, 计数, 就是depth.
    而空儿子, 
    还不知道怎么写代码
'''