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)

class Solution:
    def countNodes(self, root: TreeNode) -> int:
        # BFS
        # edge case
        if root == None:
            return 0
        
        queue = [root]
        n = 0
        while len(queue) != 0:
            l = len(queue)
            for i in range(l):
                root = queue.pop(0)
                n = n + 1
                if root.left != None:
                    queue.append(root.left)
                if root.right != None:
                    queue.append(root.right)
        return n

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

Python(III)

Time complexity = $O(n)$ , space complexity = $O(1)$ . This is the worst case, generally it's not necessary to traversal all nodes.

Be careful with two points:

1. $1+2^1+2^2+...+2^n = 2^{n+1}-1$

2. Height of left subtree is always to traversal left child, Height of right subtree is always to traversal right child. Because we want to find max height of left subtree and min height of right subtree.

class Solution:
    def countNodes(self, root: TreeNode) -> int:
        # edge case
        if root == None:
            return 0
        
        # regular case
        left = self.leftHeight(root.left)
        right = self.rightHeight(root.right)
        if left == right:
            n = pow(2, left+1) - 1
        else:
            n = 1 + self.countNodes(root.left) + self.countNodes(root.right)
            
        return n
    
    def leftHeight(self, root):
        # stop condition
        if root == None:
            return 0
        
        return 1 + self.leftHeight(root.left)
        
    def rightHeight(self, root):
        # stop condition
        if root == None:
            return 0
        
        return 1 + self.rightHeight(root.right)