Leetcode 104. Maximum Depth of Binary Tree

https://leetcode.com/problems/maximum-depth-of-binary-tree/

Even a simple problem can reflect some skills. Compare those two solutions.

Solution 1:

# T:O(n) S:O(h)
class Solution:
    # @param {TreeNode} root
    # @return {integer}
    def maxDepth(self, root):
        Solution.depth = 0
        def explore(root, depth):
            if root == None:
                if depth > Solution.depth:
                    Solution.depth = depth
                return
            explore(root.right, depth + 1)
            explore(root.left, depth + 1)
            return
        explore(root, 0)
        return Solution.depth

Run Time: 96 ms

Solution 2:

# T:O(n) S:O(h)
class Solution:
    # @param root, a tree node
    # @return an integer
    def maxDepth(self, root):
        if root is None:
            return 0
        else:    
            return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

Run Time: 76 ms