题目分析

要求对一棵二叉树进行中序遍历并返回遍历结果的列表。中序遍历的顺序是先访问左子树，然后访问根节点，最后访问右子树。这种遍历方法特别适合二叉搜索树（BST），因为它会按升序访问所有节点。

解题思路

对二叉树进行中序遍历可以使用递归或迭代方法。递归是最直接的方法，易于理解和实现。迭代方法通常使用栈来模拟递归过程，适用于深度大的树，避免递归可能导致的栈溢出问题。

递归方法：递归地访问左子树，处理根节点，再递归地访问右子树。
迭代方法：使用栈来跟踪访问的节点，模拟递归过程。

Java解法

递归解法：

import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

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

    private void inorder(TreeNode node, List<Integer> res) {
        if (node == null) {
            return;
        }
        inorder(node.left, res);  // 访问左子树
        res.add(node.val);         // 处理当前节点
        inorder(node.right, res);  // 访问右子树
    }
}

迭代解法，稍微有点难懂：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        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)，其中 n 是树中节点的数量。无论是递归还是迭代方法，每个节点都访问一次。

空间复杂度

递归解法的空间复杂度是 O(h)，其中 h 是树的高度，主要是递归栈的空间。迭代解法的空间复杂度同样是 O(h)，用于存放栈中的节点。

References

94. 二叉树的中序遍历 ↩︎

趣味算法题