222. Count Complete Tree Nodes

# Medium

Three approaches:

1. DFS traversal all nodes, and count at the same time

2. BFS traversal all nodes, and count at the same time

3. Strategy:

   1. If height(root.left) = height(root.right), then $n = 2^{height+1}$

   2. If height(root.left) > height(root.right), then n = 1+nums(root.left)+nums(root.left)

Python(I)

class Solution:
    def countNodes(self, root: TreeNode) -> int:
        # DFS
        # edge case
        if root == None:
            return 0
        
        stack = [root]
        n = 0
        while len(stack) != 0:
            root = stack.pop()
            n = n + 1
            if root.left != None:
                stack.append(root.left)
            if root.right != None:
                stack.append(root.right)
                
        return n

Because traversal all nodes, time complexity = $O(n)$ , space complexity = $O(n)$

Python(II)

Python(III)