LeetCode Binary Tree Inorder Traversal：遞歸與迭代雙解法

題目

給定二叉樹根節點，返回中序遍歷序列。要求實現遞歸與非遞歸兩種方法。

解法一：遞歸（直觀簡潔）

class Solution {
    public List inorderTraversal(TreeNode root) {
        List res = new ArrayList<>();
        dfs(root, res);
        return res;
    }
    void dfs(TreeNode node, List res) {
        if (node == null) return;
        dfs(node.left, res);
        res.add(node.val);
        dfs(node.right, res);
    }
}

解法二：迭代 + 顯式棧（模擬遞歸調用棧）

class Solution {
    public List inorderTraversal(TreeNode root) {
        List res = new ArrayList<>();
        Stack st = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !st.isEmpty()) {
            while (cur != null) { st.push(cur); cur = cur.left; }
            cur = st.pop();
            res.add(cur.val);
            cur = cur.right;
        }
        return res;
    }
}

複雜度

時間 O(n)，空間 O(h)（遞歸棧深度或顯式棧大小），h 為樹高。迭代版避免棧溢出風險。