LeetCode 314 Binary Tree Vertical Order Traversal

LeetCode

Given the root of a binary tree, return the vertical order traversal of its nodes’ values. (i.e., from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]

Example 2:

Input: root = [3,9,8,4,0,1,7]
Output: [[4],[9],[3,0,1],[8],[7]]

Example 3:

Input: root = [3,9,8,4,0,1,7,null,null,null,2,5]
Output: [[4],[9,5],[3,0,1],[8,2],[7]]

Constraints:

The number of nodes in the tree is in the range [0, 100]. -100 <= Node.val <= 100

题目大意：

按列顺序打印二叉树

BFS解题思路(推荐)：

从root开始从0编号，左右节点分别为-1, 1，如此类推，就可以标记所有节点，从而将这些节点加入结果集。

LeetCode 314 Binary Tree Vertical Order Traversal 同一列，从上到下，从左到右排序
LeetCode 987 Vertical Order Traversal of a Binary Tree 同一列，从上到下，同一行值从小到大排序

解题步骤：

N/A

注意事项：

1. BFS引入(vertical_id, root)来做计算。由于结果列表如vertical_id = -1, 1可以从左或右加入，用dict来记录vertical到list更好合理
2. 由于vertical_id是连续的，所以不妨用min_col, max_col来记录dict的范围，保证从dict到结果集是按顺序加入。

Python代码：

def verticalOrder(self, root: TreeNode) -> List[List[int]]:
	if not root:
		return []
	idx_to_list, res = collections.defaultdict(list), []
	queue = collections.deque([(0, root)])
	min_col, max_col = float('inf'), float('-inf')
	while queue:
		vertical_id, node = queue.popleft()
		min_col, max_col = min(min_col, vertical_id), max(max_col, vertical_id)
		idx_to_list[vertical_id].append(node.val)
		if node.left:
			queue.append((vertical_id - 1, node.left))
		if node.right:
			queue.append((vertical_id + 1, node.right))
	for i in range(min_col, max_col + 1):
		res.append(idx_to_list[i])
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

---

BFS算法II解题思路：

先写了这个，优化后才得到算法I。区别在于keys需要排序

Python代码：

def verticalOrder1_1(self, root: TreeNode) -> List[List[int]]:
	if not root:
		return []
	idx_to_list, res = collections.defaultdict(list), []
	queue = collections.deque([(0, root)])
	while queue:
		vertical_id, node = queue.popleft()
		idx_to_list[vertical_id].append(node.val)
		if node.left:
			queue.append((vertical_id - 1, node.left))
		if node.right:
			queue.append((vertical_id + 1, node.right))
	sorted_keys = sorted(list(idx_to_list.keys()))
	for i in sorted_keys:
		res.append(idx_to_list[i])
	return res

算法分析：

时间复杂度为O(nlogn)，空间复杂度O(n)

---

DFS算法III解题思路(不推荐)：

最开始的思路，很容易错，因为不符合题目的按层遍历的顺序。题目要求同一column的节点是从上到下，从左到右。DFS与此违反。

注意事项：

1. 要将同一个column节点从上到下从左到右排序，就要记录height和左到右的顺序(height_id, len(idx_to_list[vertical_id]) - 1, root.val)

Python代码：

def verticalOrder2(self, root: TreeNode) -> List[List[int]]:
	idx_to_list, res = collections.defaultdict(list), []
	self.dfs(root, 0, 0, idx_to_list)
	sorted_keys = sorted(list(idx_to_list.keys()))
	for i in sorted_keys:
		li = sorted(idx_to_list[i])
		res.append([node[2] for node in li])
	return res

def dfs(self, root, height_id, vertical_id, idx_to_list):
	if not root:
		return
	idx_to_list[vertical_id].append((height_id, len(idx_to_list[vertical_id]) - 1, root.val))
	self.dfs(root.left, height_id + 1, vertical_id - 1, idx_to_list)
	self.dfs(root.right, height_id + 1, vertical_id + 1, idx_to_list)

算法分析：

时间复杂度为O(nlogn)，空间复杂度O(1)