學習路線/樹 — 深度優先搜尋 (DFS)

987. 二元樹的垂直順序遍歷

Hard

Vertical Order Traversal of a Binary Tree

TreeDepth-First SearchBinary TreeHash TableSorting

題目描述

給定一棵二元樹的根節點，回傳其垂直順序遍歷的結果。從最左欄到最右欄，每欄內節點由上到下排列；若同欄同行則按值從小到大排序。

LeetCode 987原題連結 →

解法思路

  1. DFS 走訪整棵樹，根節點從 (row=0, col=0) 出發，左子 col-1、右子 col+1
  2. 每個節點將 (row, val) 加入字典 d[col] 的清單
  3. DFS 結束後，對所有欄位 col 從小到大排序
  4. 每欄內對 (row, val) tuple 清單排序（Python tuple 自動先比 row 再比 val）
  5. 取出每欄的 val 清單加入 ans，回傳

複雜度分析

  • 時間複雜度：O(n log n)
  • 空間複雜度：O(n)
3c=09c=-120c=115c=07c=2
演算法開始。建立字典 d，以欄位 c 為鍵，記錄各欄節點的 (row, val) 清單。從 dfs(root, r=0, c=0) 出發。
1 / 12