LeetCode：二叉树的中序遍历

1、题目描述

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 树中节点数目在范围 [0, 100] 内

• -100 <= Node.val <= 100

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

2、方法1：迭代

迭代法通过显式地使用栈来模拟递归的隐式栈调用，避免了递归可能导致的栈溢出问题。

步骤：

1. 初始化：创建一个空栈和一个空列表用于存储遍历结果。从根节点开始遍历。

2. 遍历左子树：

   • 将当前节点及其所有左子节点依次压入栈中，直到左子节点为空。

3. 访问节点：

   • 弹出栈顶节点（当前最左节点），将其值加入结果列表。

4. 遍历右子树：

   • 转向当前节点的右子节点，重复上述过程。

5. 终止条件：当栈为空且当前节点为空时，遍历结束。

public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = 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();list.add(current.val);// 遍历右子树current = current.right;}return list;
}

 时间复杂度：O(n)，空间复杂度：O(n)（栈空间）

3、方法2：递归

递归法直接利用函数的调用栈来实现中序遍历，代码简洁但可能因递归深度过大导致栈溢出。

步骤：

1. 递归终止条件：当前节点为空时，直接返回。

2. 递归左子树：对当前节点的左子节点调用递归函数。

3. 访问节点：将当前节点的值加入结果列表。

4. 递归右子树：对当前节点的右子节点调用递归函数。

public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();middleTree(root, list);return list;
}public void middleTree(TreeNode node, List list) {if (node == null) return;middleTree(node.left, list);  // 递归左子树list.add(node.val);           // 访问节点middleTree(node.right, list); // 递归右子树
}

 时间复杂度：O(n)，空间复杂度：O(n)（调用栈）