題目描述
這是 LeetCode 上的 590. N 叉樹的後序周遊 ，難度為 簡單。
Tag : 「遞歸」、「疊代」、「非遞歸」、「DFS」、「BFS」
給定一個 叉樹的根節點 ，傳回 其節點值的 後序周遊 。
叉樹 在輸入中按層序周遊進行序列化表示，每組子節點由空值
null
分隔（請參見示例）。
示例 1：
輸入：root = [1,null,3,2,4,null,5,6]
輸出：[5,6,3,2,4,1] 示例 2：
輸入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
輸出：[2,6,14,11,7,3,12,8,4,13,9,10,5,1] 提示：
- 節點總數在範圍内
- 叉樹的高度小于或等于
進階：遞歸法很簡單，你可以使用疊代法完成此題嗎?
遞歸
正常做法，不再贅述。
代碼：
class Solution {
List<Integer> ans = new ArrayList<>();
public List<Integer> postorder(Node root) {
dfs(root);
return ans;
}
void dfs(Node root) {
if (root == null) return;
for (Node node : root.children) dfs(node);
ans.add(root.val);
}
} - 時間複雜度：
- 空間複雜度：忽略遞歸帶來的額外空間開銷，複雜度為
非遞歸
針對本題，使用「棧」模拟遞歸過程。
疊代過程中記錄
(cnt = 目前節點周遊過的子節點數量, node = 目前節點)
二進制組，每次取出棧頂元素，如果目前節點已經周遊完所有的子節點（目前周遊過的子節點數量為 ），則将目前節點的值加入答案。
否則更新目前元素周遊過的子節點數量，并重新入隊，即将 入隊，以及将下一子節點 進行首次入隊。
代碼：
class Solution {
public List<Integer> postorder(Node root) {
List<Integer> ans = new ArrayList<>();
Deque<Object[]> d = new ArrayDeque<>();
d.addLast(new Object[]{0, root});
while (!d.isEmpty()) {
Object[] poll = d.pollLast();
Integer cnt = (Integer)poll[0]; Node t = (Node)poll[1];
if (t == null) continue;
if (cnt == t.children.size()) ans.add(t.val);
if (cnt < t.children.size()) {
d.addLast(new Object[]{cnt + 1, t});
d.addLast(new Object[]{0, t.children.get(cnt)});
}
}
return ans;
}
} - 時間複雜度：
- 空間複雜度：
通用「非遞歸」
另外一種「遞歸」轉「疊代」的做法，是直接模拟系統執行「遞歸」的過程，這是一種更為通用的做法。
由于現代編譯器已經做了很多關于遞歸的優化，現在這種技巧已經無須掌握。
在疊代過程中記錄目前棧幀位置狀态
loc
，在每個狀态流轉節點做相應操作。
代碼：
class Solution {
public List<Integer> postorder(Node root) {
List<Integer> ans = new ArrayList<>();
Deque<Object[]> d = new ArrayDeque<>();
d.addLast(new Object[]{0, root});
while (!d.isEmpty()) {
Object[] poll = d.pollLast();
Integer loc = (Integer)poll[0]; Node t = (Node)poll[1];
if (t == null) continue;
if (loc == 0) {
d.addLast(new Object[]{1, t});
int n = t.children.size();
for (int i = n - 1; i >= 0; i--) d.addLast(new Object[]{0, t.children.get(i)});
} else if (loc == 1) {
ans.add(t.val);
}
}
return ans;
}
} - 時間複雜度：
- 空間複雜度：
最後
這是我們「刷穿 LeetCode」系列文章的第
No.590
篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。