Hot100 - 二叉树的中序遍历
最佳思路：
- 中序遍历的顺序是：左子树 -> 根节点 -> 右子树。为了实现这个顺序，我们可以利用栈来模拟递归过程，从而避免栈溢出的问题。
- 在遍历过程中，始终向左子树深入，直到叶子节点为止，然后回溯并访问节点，再转向右子树。
时间复杂度：
- 时间复杂度为 O(n)，其中 n 为二叉树的节点数。每个节点都被访问一次，因此时间复杂度为线性。
- 空间复杂度为 O(h)，其中 h 是二叉树的高度。最坏情况下，栈的空间复杂度为树的高度，即树为完全不平衡时为 O(n)，最优情况下为平衡二叉树时为 O(log n)。
思路解析：
- 使用栈模拟递归：在中序遍历中，首先访问左子树，再访问根节点，最后访问右子树。传统的递归方式非常直观，但栈的实现可以有效避免递归深度过大导致栈溢出的风险。
- 模拟遍历过程：我们从根节点开始，反复将当前节点及其左子树压入栈中。直到左子树为空（即叶子节点），然后开始弹出栈中的节点并访问它们，接着访问其右子树。这样可以确保中序遍历的顺序。
- 边界条件处理：需要在栈为空并且当前节点为空时停止遍历，确保程序不会无限循环。
代码实现：
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();while (stack.size() > 0 || root != null) {if (root != null) {stack.add(root);root = root.left; } else {TreeNode tmp = stack.pop();res.add(tmp.val);root = tmp.right;}}return res;}
}
思路总结：
- 本题的关键在于如何通过栈模拟递归来实现中序遍历。通过控制栈的操作，我们能够按顺序遍历每一个节点，避免递归的深度问题。相较于传统递归，迭代的栈方式在某些场景下能更好地控制空间复杂度，尤其是在树结构较大时。
