94.二叉树的中序遍历

题目:94.二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

• 示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

• 示例 2：

输入：root = []
输出：[]

• 示例 3：

输入：root = [1]
输出：[1]

• 提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

• 进阶：

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

思路1

递归方法
递归方法: 我们定义一个辅助函数 inorderHelper，它接收一个节点作为参数，递归地处理左子树、根节点和右子树。

• 时间复杂度:O(n)，其中 n 是二叉树的节点数
• 空间复杂度:O(h)，其中 h 是二叉树的高度

代码

// 递归中序遍历方法
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new LinkedList<>();
    if (root == null) {
        return result;
    }
    inorderHelper(result, root);
    return result;
}

// 递归辅助方法
private void inorderHelper(List<Integer> result, TreeNode node) {
    if (node == null) {
        return;
    }
    // 遍历左子树
    inorderHelper(result, node.left);
    // 访问根节点
    result.add(node.val);
    // 遍历右子树
    inorderHelper(result, node.right);
}

思路2

迭代方法: 使用栈来模拟递归的过程。

1. 我们使用一个栈来存储节点，在遍历过程中先将左子树节点压入栈中，并使用 current 变量用于当前遍历节点。
2. 进入循环，每次将当前节点的左子节点压入栈中，直到当前节点为空。
3. 然后访问根节点，最后访问右子树。

• 时间复杂度:O(n)
• 空间复杂度:O(n)

代码

// 迭代中序遍历方法
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new LinkedList<>();
    if (root == null) {
        return result;
    }
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;
    while (current != null || !stack.empty()) {
        while (current != null) {
            // 将左子树节点压入栈中
            stack.push(current);
            current = current.left;
        }
        // 访问根节点
        current = stack.pop();
        result.add(current.val);
        // 访问右子树
        current = current.right;
    }
    return result;
}