Python Solutions with Detailed Explanations


  • 1
    G

    Solution

    Maximum Depth of Binary Tree https://leetcode.com/problems/maximum-depth-of-binary-tree/

    Depth First Search: Post Order

    • Empty tree i.e. root is None: Depth = 0
    • maxDepth(root) = max(maxDepth(root.left), maxDepth(root.right)) + 1
    • Time and Space Complexity: O(N)
    class Solution_DFS_Post_Order(object):
        def maxDepth(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            if root is None:
                return 0
            else:
                return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
    

    Depth First Search: PreOrder

    • Perform pre-order traversal and pass a variable to track the level
    • Time and Space Complexity: O(N)
    from collections import deque
    class Solution_BFS_Iterative(object):
        def maxDepth(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            q, depth = deque(), 0
            if root:
                q.append(root)
            while len(q):
                depth += 1
                for _ in range(len(q)):
                    x = q.popleft()
                    if x.left:
                        q.append(x.left)
                    if x.right:
                        q.append(x.right)
            return depth
    

    Depth First Search: Iterative Version

    • Push the root and the level on the stack.
    • Pop and push left and right kids of root. Update the max_level variable.
    • Time and Space Complexity: O(N)
    class Solution_DFS_Pre_Order(object):
        def maxDepth(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            self.max_level = 0
            self.helper(root, 0)
            return self.max_level
        
        def helper(self, root, level):
            self.max_level = max(self.max_level, level)
            if root:
                self.helper(root.left, level+1)
                self.helper(root.right, level+1)
            return
    

    Breadth First Search: Iterative Version

    • Traverse level by level and keep a counter to track level count
    • Time and Space Complexity: O(N)
    class Solution(object):
        def maxDepth(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            st, max_level = [], 0
            if root:
                st.append((root, 1))
            while st:
                x, level = st.pop()
                max_level = max(max_level, level)
                if x.left:
                    st.append((x.left, level+1))
                if x.right:
                    st.append((x.right, level+1))
            return max_level
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.