Binary Tree Vertical Order Traversal

题目描述

Given a binary tree, return the vertical order traversal of its nodes' values. (ie, from top to bottom, column by column).

Examples: Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its vertical order traversal as:

[
  [9],
  [3,15],
  [20],
  [7]
]

解题方法

第一次看到估计懵B， 拿到题目先画几个例子，找实例，clarify问题永远是最重要的！

基本上二叉树的问题，类型就是recursive, DFS, BFS,blablabla。这个题目应该也差不多， recursive打印肯定不行，但是遍历整个树找找感觉还是可以的。我们做过level order traversal,这里是按照列的方式traversal，那么如何知道当前node的列数呢？

我们可以自己define，比如例子里面

• 第一列 9
• 第二列 3， 15
• 第三列 20
• 第四列 7

暂时是这样，但是并没有太大帮助，我们又可以发现root 3 和node 15是同一列的，而 root到15的路径是怎样的呢？root -> 右 -> 左 -> 15，发现左右抵消了。所以可以进一步 define列数，向左就减1，向右就加1。

到这里基本上就应该知道怎么做了，根据这个定义求出所有node的“列数”，然后将相同 列数的放到同一个array里。

方法1

只用O(1)的space，找出列数的上下限，然后再遍历找出分别对应当前列数的node

time complexity: O(w * n), w是列数的范围，worst case是O(n^2)

方法2

第一种方法要不断地遍历整个树，肯定不是optimal的，使用O（n）的space建一个hashtable, key:value是 {列：[node1, node2, node2]}，这样遍历一遍，然后打印就可以了。

在leetcode上还要求同一列的要从上往下打印，所以还要记录下行数，将行数和node一起存在 一个tuple里就好了

Solution

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

# h_d means horizontal distance
# get h_d for each node, and save into hashmap
# left means h_d - 1, right means h_d + 1

class Solution(object):

    def __init__(self):
        self.min_hd = sys.maxint
        self.max_hd = -sys.maxint

    def verticalOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []

        d_n_map = {}
        result = []
        self.getNodeHD(root, 0, d_n_map, 0)

        for i in range(self.min_hd, self.max_hd+1):
            cur_list = d_n_map[i]
            # 根据vertical distance sort
            cur_list = sorted(cur_list, key=lambda n: n[1])
            new_list = map(lambda n: n[0], cur_list) # map function
            result.append(new_list)

        return result

    def getNodeHD(self, root, hd, d_n_map, vd):
        if not root:
            return
        if hd < self.min_hd:
            self.min_hd = hd
        if hd > self.max_hd:
            self.max_hd = hd
        if hd in d_n_map:
            d_n_map[hd].append((root.val, vd))
        else:
            d_n_map[hd] = [(root.val, vd)]

        self.getNodeHD(root.left, hd-1, d_n_map, vd+1)
        self.getNodeHD(root.right, hd+1, d_n_map, vd+1)

Reference

• geeksforgeeks 1
• geeksforgeeks 2