Python BFS with comments

  • 0
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution(object):
        def levelOrder(self, root):
            :type root: TreeNode
            :rtype: List[List[int]]
            # First find out height 
            height = self.height(root)
            result = []
            # Here the approch is BFS 
            # Hence to simulate these conditions we will use simple for loop 
            for i in range(height):
                result.append(self.printLevelOrder(root,i, []))
            return result
        # This function basically reaches to the level first then appends result to it 
        def printLevelOrder(self, node, height, result):
            if node == None:
            # If reached to level add val
            if(height == 0):
            # Else go left and right with one less level
            # Here what you are doing is that decreasing height by 1 until you get height 0 which is nothing but desired level
            # So lets say we want to reach level 2 then we will pass height as 2 then decrease it till becomes zero and simultanously go deep               into tree at every recursive call
            if height > 0:
                self.printLevelOrder(node.left, height-1, result)
                self.printLevelOrder(node.right, height-1, result)
            return result
        # Find out height 
        def height(self, root):
            if root == None:
                return 0
            return 1+ max(self.height(root.left),self.height(root.right))

Log in to reply

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