What a problem full of fun! (Python pre-order Solution)


  • 0
    1. First declare a list ans as the final answer.
    2. Pre-order iterate this tree
    3. Find the right place the new node should be
    4. if the list doesn't fit the size then just expend it
    class Solution(object):
        def verticalOrder(self, root):
            ans, rk = [], []
            if not root:
                return []
            def preorder(r, prank, lv):
                if not r:
                    return
                while len(ans) <= prank:
                    ans.append([])
                    rk.append([])
                idx = bisect.bisect_right(rk[prank], lv)
                ans[prank].insert(idx, r.val)
                rk[prank].insert(idx, lv)
                preorder(r.left, prank - 1, lv + 1)
                preorder(r.right, prank + 1, lv + 1)
            preorder(root, 5, 0)
            ans = filter(lambda x: len(x) != 0, ans)
            return ans
    

Log in to reply
 

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