vvrf / DSA.log

问题拆解

中序遍历的规则是：先访问左子树，再访问根，最后访问右子树。递归写法几乎不用动脑，但题目进阶要求用迭代完成，这才是值得琢磨的地方。

难点在于：递归之所以简单，是因为函数调用栈帮我们记住了“处理完左子树后，还得回到当前节点、再去处理右子树”。改成迭代，就得自己用一个栈把这条“回头路”显式管理起来。

迭代版遍历的本质，是手动复刻递归调用栈干的活。

递归写法

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    visit(root, result);
    return result;
}

private void visit(TreeNode node, List<Integer> result) {
    if (node == null) return;
    visit(node.left, result);
    result.add(node.val);
    visit(node.right, result);
}

def inorderTraversal(root):
    result = []

    def visit(node):
        if not node:
            return
        visit(node.left)
        result.append(node.val)
        visit(node.right)

    visit(root)
    return result

func inorderTraversal(root *TreeNode) []int {
    result := []int{}
    var visit func(node *TreeNode)
    visit = func(node *TreeNode) {
        if node == nil {
            return
        }
        visit(node.Left)
        result = append(result, node.Val)
        visit(node.Right)
    }
    visit(root)
    return result
}

pub fn inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    let mut result = Vec::new();
    fn visit(node: &Option<Rc<RefCell<TreeNode>>>, result: &mut Vec<i32>) {
        if let Some(n) = node {
            let n = n.borrow();
            visit(&n.left, result);
            result.push(n.val);
            visit(&n.right, result);
        }
    }
    visit(&root, &mut result);
    result
}

三行顺序就是中序定义本身，改一改顺序就能得到前序或后序。

显式栈迭代

用一个指针 cur 一路向左把节点压栈，走到底后弹出访问，再转向它的右子树：

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        result.add(cur.val);
        cur = cur.right;
    }
    return result;
}

def inorderTraversal(root):
    result, stack = [], []
    cur = root

    while cur or stack:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        result.append(cur.val)
        cur = cur.right

    return result

func inorderTraversal(root *TreeNode) []int {
    result := []int{}
    stack := []*TreeNode{}
    cur := root
    for cur != nil || len(stack) > 0 {
        for cur != nil {
            stack = append(stack, cur)
            cur = cur.Left
        }
        cur = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        result = append(result, cur.Val)
        cur = cur.Right
    }
    return result
}

pub fn inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    let mut result = Vec::new();
    let mut stack = Vec::new();
    let mut cur = root;
    while cur.is_some() || !stack.is_empty() {
        while let Some(node) = cur {
            cur = node.borrow().left.clone();
            stack.push(node);
        }
        let node = stack.pop().unwrap();
        result.push(node.borrow().val);
        cur = node.borrow().right.clone();
    }
    result
}

内层循环负责“尽量往左”，弹栈时机就对应递归里“左子树处理完了”的那一刻，访问完当前值后把 cur 指向右孩子，循环会自动对右子树重复同样的过程。

复杂度

指标	复杂度	原因
时间	`O(n)`	每个节点入栈、出栈各一次
空间	`O(h)`	栈里最多存一条从根到当前节点的路径

可以迁移的模式

任何递归都能用显式栈改写成迭代，关键是想清楚“栈里存的是待返回的现场”；
“一路向某个方向走到底，再回退”的结构，天然对应压栈—弹栈；
遍历顺序的差异只在访问根节点的时机，框架可以复用。

当递归深度可能失控、或面试要求手写栈时，这套“模拟调用栈”的思路就派上用场了。