LeetCode 94 Binary Tree Inorder Traversal：非遞歸棧模擬中序遍歷

題目描述

給定二叉樹根節點，返回其中序遍歷序列。**不使用遞歸**。

範例

Input: [1,null,2,3]  (1 右子 2，2 左子 3)
   1
    \
     2
    /
   3
Output: [1,3,2]

棧模擬遞歸邏輯

中序：左 → 根 → 右。用棧保存「待處理的左鏈」。

演算法流程

1. p = root。
2. 沿左子樹下行，將沿途節點壓入棧，直到 p == nullptr。
3. 彈出棧頂 p，訪問其值（中序位置）。
4. 轉向 p->right，重複步驟 2。
5. 直到棧空且 p == nullptr。

Python 參考實作

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def inorderTraversal(self, root):
        result, stack = [], []
        p = root
        while p or stack:
            while p:
                stack.append(p)
                p = p.left
            p = stack.pop()
            result.append(p.val)
            p = p.right
        return result

C++ 版本

class Solution {
public:
    vector inorderTraversal(TreeNode* root) {
        vector res;
        stack st;
        TreeNode* p = root;
        while (p || !st.empty()) {
            while (p) {
                st.push(p);
                p = p->left;
            }
            p = st.top(); st.pop();
            res.push_back(p->val);
            p = p->right;
        }
        return res;
    }
};

複雜度

• 時間：O(n)，每節點進出棧各一次。
• 空間：O(h)，h 為樹高（最壞 O(n)）。

Morris 遍歷（O(1) 空間，選讀）

利用葉節點右指標為空建立執緒，遍歷後恢復。代碼較複雜，面試常考。