Python solution with detailed explanation


  • 0
    G

    Solution

    Binary Tree Vertical Order Traversal https://leetcode.com/problems/binary-tree-vertical-order-traversal/

    Preorder Traversal

    • Do a pre-order traversal and maintain two variables to track depth and width. depth is incremented level by level. width increases by 1 when we go right and decreases by 1 when we go left.
    • Maintain a dictionary to store preorder values. The key is the width. Value is the sub dictionary with different depths. Pre-order makes sure we get left to right.
    from pprint import pprint
    from collections import defaultdict
    class Solution(object):
        def verticalOrder(self, root):
            """
            :type root: TreeNode
            :rtype: List[List[int]]
            """
            cache = defaultdict(lambda : defaultdict(list))
            self.helper(root, 0, 0, cache)
            result = []
            for width in sorted(cache.keys()):
                result.append([])
                for depth in sorted(cache[width].keys()):
                    for x in cache[width][depth]:
                        result[-1].append(x)
            return result
        
        def helper(self, root, width, depth, cache):
            if root == None:
                return
            cache[width][depth].append(root.val)
            self.helper(root.left, width-1, depth+1, cache)
            self.helper(root.right, width+1, depth+1, cache)
            return
    

    Level Order

    • Do a level order traversal. Keep track of width and store in a dictionary.
    • level order makes sure top to bottom is maintained. Order of adding children is left to right and that makes sure left to right constraint.
    from collections import defaultdict, deque
    class Solution(object):
        def verticalOrder(self, root):
            """
            :type root: TreeNode
            :rtype: List[List[int]]
            """
            if root == None:
                return []
            cache = defaultdict(list)
            q = deque()
            q.append((root, 0))
            while len(q):
                x,width = q.popleft()
                cache[width].append(x.val)
                if x.left:
                    q.append((x.left, width-1))
                if x.right:
                    q.append((x.right, width+1))
            result = []
            for i in sorted(cache.keys()):
                result.append(cache[i])
            return result
    

Log in to reply
 

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