Straightforward python solution by using InOrder Traversal


  • 0
    Y
    # 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 verticalOrder(self, root):
            """
            :type root: TreeNode
            :rtype: List[List[int]]
            """
            nodes = []
            sz = {}
            def inOrder(root,x,y):
                if not root:
                   return
                inOrder(root.left,x+1,y-1)
                nodes.append((root.val,x,y))
                if y not in sz:
                   sz[y] = 1
                else:
                   sz[y] = sz[y] + 1    
                inOrder(root.right,x+1,y+1)
            inOrder(root, 0, 0)
            ans = []
            if nodes:
                nodes.sort(key=lambda x: (x[2], x[1]))
                nextSize = sz[nodes[0][2]]
                currSize = 0
                curr = []
                for node in nodes:
                    if currSize == nextSize:
                       nextSize = sz[node[2]]
                       currSize = 0
                       ans.append(curr)
                       curr = []
                    curr.append(node[0])
                    currSize += 1
                ans.append(curr)    
            return ans

Log in to reply
 

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