萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

二叉樹非遞歸後序遍歷算法詳解(雙棧法、單棧標記法、Morris 遍歷)

後序遍歷順序:左 → 右 → 根

非遞歸實現難點:訪問根節點時,需確保左右子樹**均已完全訪問**。遞歸利用調用棧天然記錄狀態,非遞歸需顯式維護狀態。

方法一:雙棧法(最直觀)

原理

  1. 棧 1:按「根 → 右 → 左」順序壓入節點(類似前序的鏡像)。
  2. 棧 2:彈出棧 1 節點時壓入棧 2。
  3. 最終棧 2 彈出順序即為「左 → 右 → 根」。

代碼

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)。

方法二:單棧 + 前驅指針/訪問標記(經典單棧)

原理

  • 模擬遞歸棧,需知道「是否已處理完右子樹」。
  • 用 `prev` 記錄上一次訪問的節點:若 `prev` 是當前節點的右孩子,或無右孩子且 `prev` 是左孩子,說明右子樹已處理完,可訪問根。

代碼

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; // 右子樹是否已訪問
}

算法流程(對應原文)

  1. 從根開始,沿左孩子入棧,`rightVisited=false`。
  2. 循環:取棧頂 `sn`。
    • 若 `sn.node` 無右孩子 或 `sn.rightVisited=true` → 訪問該節點,出棧。
    • 否則:設置 `sn.rightVisited=true`,轉向右孩子,並將右孩子及其左鏈全部入棧 (`rightVisited=false`)。

代碼實現

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;
}

方法四:Morris 後序遍歷(O(1) 空間,修改樹結構)

利用線索化樹思想,建立臨時鏈接回溯,遍歷完成後恢復樹結構。代碼較複雜,此處略過,面試重點了解思路即可。

對比總結

方法空間修改樹理解難度推薦場景
雙棧O(n)否低教學、快速實現
單棧 + prevO(h)否中面試、生產環境通用
單棧 + 標記O(h)否中高邏輯清晰、易擴展
MorrisO(1)臨時修改高極限空間受限環境

遞歸版本(參考)

function postorderRecursive(root, res = []) {
    if (!root) return;
    postorderRecursive(root.left, res);
    postorderRecursive(root.right, res);
    res.push(root.val);
    return res;
}
copyright © 萬盛學電腦網 all rights reserved