二叉树中序遍历：递归与显式栈

核心结论#

中序遍历的顺序是左子树、根节点、右子树。递归实现最直观；当树可能很深、需要主动控制调用栈时，可以使用显式栈完成同样的状态管理。

问题#

给定二叉树根节点 root，返回其中序遍历结果。例如 root = [1, null, 2, 3] 的结果为 [1, 3, 2]。

递归实现#

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

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

结果列表放在方法内部，避免同一个 Solution 实例被重复调用时残留上一次结果。

迭代实现#

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode current = root;

        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            result.add(current.val);
            current = current.right;
        }
        return result;
    }
}

正确性与复杂度#

两种实现都保证每个节点在其左子树之后、右子树之前被加入结果。每个节点访问一次，时间复杂度为 O(n)；递归栈或显式栈最多保存树高 h 个节点，空间复杂度为 O(h)。

验证#

覆盖空树、单节点、只有左子树、只有右子树，以及完全二叉树。空树必须返回空列表，而不是 null。

参考#

• LeetCode 94：二叉树的中序遍历
• Java Deque