非遞歸實現難點:訪問根節點時,需確保左右子樹**均已完全訪問**。遞歸利用調用棧天然記錄狀態,非遞歸需顯式維護狀態。
function postorderTwoStacks(root) {
if (!root) return [];
var s1 = [root], s2 = [];
while (s1.length) {
var node = s1.pop();
s2.push(node);
if (node.left) s1.push(node.left); // 先左後右入 s1,出棧順序為右→左
if (node.right) s1.push(node.right);
}
var result = [];
while (s2.length) {
result.push(s2.pop().val);
}
return result;
}
時間 O(n),空間 O(n)。
function postorderOneStack(root) {
if (!root) return [];
var stack = [], result = [], prev = null;
var curr = root;
while (curr || stack.length) {
while (curr) { // 一路向左
stack.push(curr);
curr = curr.left;
}
curr = stack[stack.length - 1]; // 查看棧頂
// 無右子樹 或 右子樹剛被訪問過
if (!curr.right || curr.right === prev) {
result.push(curr.val);
stack.pop();
prev = curr;
curr = null; // 重要:避免重複進入左子樹循環
} else {
curr = curr.right; // 轉向右子樹
}
}
return result;
}
// 棧元素包裝器
function StackNode(node, rightVisited) {
this.node = node;
this.rightVisited = rightVisited; // 右子樹是否已訪問
}
function postorderMarkedStack(root) {
if (!root) return [];
var stack = [], result = [];
var p = root;
// 1. 初始化:沿左鏈入棧
while (p) {
stack.push({ node: p, rightVisited: false });
p = p.left;
}
while (stack.length) {
var top = stack[stack.length - 1];
var node = top.node;
// 2. 可訪問條件:無右子樹 或 右子樹已訪問
if (!node.right || top.rightVisited) {
result.push(node.val);
stack.pop();
} else {
// 3. 處理右子樹:標記、轉向右、壓入右子樹左鏈
top.rightVisited = true;
p = node.right;
while (p) {
stack.push({ node: p, rightVisited: false });
p = p.left;
}
}
}
return result;
}
利用線索化樹思想,建立臨時鏈接回溯,遍歷完成後恢復樹結構。代碼較複雜,此處略過,面試重點了解思路即可。
| 方法 | 空間 | 修改樹 | 理解難度 | 推薦場景 |
|---|---|---|---|---|
| 雙棧 | O(n) | 否 | 低 | 教學、快速實現 |
| 單棧 + prev | O(h) | 否 | 中 | 面試、生產環境通用 |
| 單棧 + 標記 | O(h) | 否 | 中高 | 邏輯清晰、易擴展 |
| Morris | O(1) | 臨時修改 | 高 | 極限空間受限環境 |
function postorderRecursive(root, res = []) {
if (!root) return;
postorderRecursive(root.left, res);
postorderRecursive(root.right, res);
res.push(root.val);
return res;
}