題目描述
這是 LeetCode 上的 987. 二叉樹的垂序周遊 ，難度為 困難。
Tag : 「資料結構運用」、「二叉樹」、「哈希表」、「排序」、「優先隊列（堆）」、「DFS」
給你二叉樹的根結點
root
，請你設計算法計算二叉樹的 垂序周遊 序列。
對位于 的每個結點而言，其左右子結點分别位于 和 。樹的根結點位于
二叉樹的 垂序周遊 從最左邊的列開始直到最右邊的列結束，按列索引每一列上的所有結點，形成一個按出現位置從上到下排序的有序清單。如果同行同列上有多個結點，則按結點的值從小到大進行排序。
傳回二叉樹的 垂序周遊 序列。
示例 1：
輸入：root = [3,9,20,null,null,15,7]
輸出：[[9],[3,15],[20],[7]] 示例 2：
輸入：root = [1,2,3,4,5,6,7]
輸出：[[4],[2],[1,5,6],[3],[7]] 示例 3：
輸入：root = [1,2,3,4,6,5,7]
輸出：[[4],[2],[1,5,6],[3],[7]] 提示：
- 樹中結點數目總數在範圍
DFS + 哈希表 + 排序
根據題意，我們需要按照優先級「“列号從小到大”，對于同列節點，“行号從小到大”，對于同列同行元素，“節點值從小到大”」進行答案構造。
是以我們可以對樹進行周遊，周遊過程中記下這些資訊 ，然後根據規則進行排序，并構造答案。
我們可以先使用「哈希表」進行存儲，最後再進行一次性的排序。
代碼：
class Solution {
Map<TreeNode, int[]> map = new HashMap<>(); // col, row, val
public List<List<Integer>> verticalTraversal(TreeNode root) {
map.put(root, new int[]{0, 0, root.val});
dfs(root);
List<int[]> list = new ArrayList<>(map.values());
Collections.sort(list, (a, b)->{
if (a[0] != b[0]) return a[0] - b[0];
if (a[1] != b[1]) return a[1] - b[1];
return a[2] - b[2];
});
int n = list.size();
List<List<Integer>> ans = new ArrayList<>();
for (int i = 0; i < n; ) {
int j = i;
List<Integer> tmp = new ArrayList<>();
while (j < n && list.get(j)[0] == list.get(i)[0]) tmp.add(list.get(j++)[2]);
ans.add(tmp);
i = j;
}
return ans;
}
void dfs(TreeNode root) {
if (root == null) return ;
int[] info = map.get(root);
int col = info[0], row = info[1], val = info[2];
if (root.left != null) {
map.put(root.left, new int[]{col - 1, row + 1, root.left.val});
dfs(root.left);
}
if (root.right != null) {
map.put(root.right, new int[]{col + 1, row + 1, root.right.val});
dfs(root.right);
}
}
} - 時間複雜度：令總節點數量為，填充哈希表時進行樹的周遊，複雜度為；構造答案時需要進行排序，複雜度為。整體複雜度為
- 空間複雜度：
DFS + 優先隊列（堆）
顯然，最終要讓所有節點的相應資訊有序，可以使用「優先隊列（堆）」邊存儲邊維護有序性。
代碼：
class Solution {
PriorityQueue<int[]> q = new PriorityQueue<>((a, b)->{ // col, row, val
if (a[0] != b[0]) return a[0] - b[0];
if (a[1] != b[1]) return a[1] - b[1];
return a[2] - b[2];
});
public List<List<Integer>> verticalTraversal(TreeNode root) {
int[] info = new int[]{0, 0, root.val};
q.add(info);
dfs(root, info);
List<List<Integer>> ans = new ArrayList<>();
while (!q.isEmpty()) {
List<Integer> tmp = new ArrayList<>();
int[] poll = q.peek();
while (!q.isEmpty() && q.peek()[0] == poll[0]) tmp.add(q.poll()[2]);
ans.add(tmp);
}
return ans;
}
void dfs(TreeNode root, int[] fa) {
if (root.left != null) {
int[] linfo = new int[]{fa[0] - 1, fa[1] + 1, root.left.val};
q.add(linfo);
dfs(root.left, linfo);
}
if (root.right != null) {
int[] rinfo = new int[]{fa[0] + 1, fa[1] + 1, root.right.val};
q.add(rinfo);
dfs(root.right, rinfo);
}
}
} - 時間複雜度：令總節點數量為，将節點資訊存入優先隊列（堆）複雜度為；構造答案複雜度為。整體複雜度為
- 空間複雜度：
DFS + 哈希嵌套 + 排序
當然，如果想鍛煉一下自己的代碼能力，不使用三元組
用三個「哈希表」來記錄相關資訊：
- 使用
node2row
node2col
dfs1
- 使用
col2row2nodes
{col : {row : [node1, node2, ... ]}}
dfs2
node2row
node2col
col2row2nodes
- 按照題意，按「列号從小到大」，對于同列節點，按照「行号從小到大」，對于同列同行元素，按照「節點值從小到大」的規則，使用
col2row2nodes
注意：本解法可以隻進行一次樹的周遊，分兩步主要是不想 dfs
代碼：
class Solution {
Map<TreeNode, Integer> node2col = new HashMap<>(), node2row = new HashMap<>();
Map<Integer, Map<Integer, List<Integer>>> col2row2nodes = new HashMap<>();
public List<List<Integer>> verticalTraversal(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
node2col.put(root, 0);
node2row.put(root, 0);
dfs1(root);
dfs2(root);
List<Integer> cols = new ArrayList<>(col2row2nodes.keySet());
Collections.sort(cols);
for (int col : cols) {
Map<Integer, List<Integer>> row2nodes = col2row2nodes.get(col);
List<Integer> rows = new ArrayList<>(row2nodes.keySet());
Collections.sort(rows);
List<Integer> cur = new ArrayList<>();
for (int row : rows) {
List<Integer> nodes = row2nodes.get(row);
Collections.sort(nodes);
cur.addAll(nodes);
}
ans.add(cur);
}
return ans;
}
// 樹的周遊，根據「節點到列」&「節點到行」的映射關系，構造出「從列到行，從行到節點集」的映射關系
void dfs2(TreeNode root) {
if (root == null) return ;
int col = node2col.get(root), row = node2row.get(root);
Map<Integer, List<Integer>> row2nodes = col2row2nodes.getOrDefault(col, new HashMap<>());
List<Integer> nodes = row2nodes.getOrDefault(row, new ArrayList<>());
nodes.add(root.val);
row2nodes.put(row, nodes);
col2row2nodes.put(col, row2nodes);
dfs2(root.left);
dfs2(root.right);
}
// 樹的周遊，記錄下「節點到列」&「節點到行」的映射關系
void dfs1(TreeNode root) {
if (root == null) return ;
if (root.left != null) {
int col = node2col.get(root);
node2col.put(root.left, col - 1);
int row = node2row.get(root);
node2row.put(root.left, row + 1);
dfs1(root.left);
}
if (root.right != null) {
int col = node2col.get(root);
node2col.put(root.right, col + 1);
int row = node2row.get(root);
node2row.put(root.right, row + 1);
dfs1(root.right);
}
}
} - 時間複雜度：令總的節點數量為，填充幾個哈希表的複雜度為；構造答案時需要對行号、列号和節點值進行排序，總的複雜度上界為。整體複雜度為
- 空間複雜度：
最後
這是我們「刷穿 LeetCode」系列文章的第
No.987
篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。
在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。