二叉树的中序遍历是一种常见的树遍历算法，它的遍历顺序是先遍历左子树，然后访问根节点，最后遍历右子树。在遍历过程中，我们将节点的值按照这个顺序添加到一个列表中。
对于这个问题，我们可以使用递归或迭代或莫里斯遍历的方法来实现中序遍历。下面我将分别介绍这三种方法的思路：
递归方法
递归方法是实现中序遍历最直观的方式。递归的基本思想是：
- 如果当前节点为 null，直接返回。
- 递归遍历当前节点的左子树。
- 访问当前节点，将其值添加到结果列表中。
- 递归遍历当前节点的右子树。
递归方法的代码实现通常如下所示：
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();helper(root, result);return result;}private void helper(TreeNode node, List<Integer> result) {if (node == null) {return;}helper(node.left, result); // 遍历左子树result.add(node.val); // 访问节点helper(node.right, result); // 遍历右子树}
}迭代方法
迭代方法通常使用栈来模拟递归过程。迭代中序遍历的基本步骤是：
- 创建一个空栈，用于存储节点。
- 从根节点开始，将所有左子节点压入栈中。
- 当栈不为空或者当前节点不为空时，执行以下操作：
- 弹出栈顶元素，并将其值添加到结果列表中。
- 将当前节点设置为弹出节点的右子节点，然后继续将所有左子节点压入栈中。
- 重复步骤3，直到栈为空且当前节点为 null。
迭代方法的代码实现通常如下所示：
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;}
}在这两种方法中，递归方法更简洁直观，但可能会遇到栈溢出的问题，特别是对于非常深的树。迭代方法则可以避免这个问题，但代码相对复杂一些。在实际应用中，可以根据具体情况选择合适的方法。
莫里斯遍历（Morris Traversal）
是一种用于二叉树遍历的方法，它不使用任何额外的存储空间（递归或栈），而是通过在树中添加临时指针来实现遍历。莫里斯遍历可以进行中序、前序和后序遍历，这里我们主要讨论中序莫里斯遍历。
中序莫里斯遍历的基本思路是：
- 遍历二叉树的每个节点。
- 对于每个节点，如果它没有左子节点，直接访问它（这是中序遍历的特点）。
- 如果节点有左子节点，找到左子树中最右边的节点（左子树的“前驱”节点），并在那里添加一个指向当前节点的临时链接。
- 通过这个临时链接，将当前节点的左子节点设置为 null，然后递归地进行中序遍历。
- 完成遍历后，删除所有添加的临时链接，恢复树的原始结构。
下面是中序莫里斯遍历的代码实现：
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();TreeNode current = root;while (current != null) {if (current.left == null) {// 如果没有左子节点，直接访问result.add(current.val);current = current.right;} else {// 找到左子树中最右边的节点TreeNode predecessor = current.left;while (predecessor.right != null && predecessor.right != current) {predecessor = predecessor.right;}if (predecessor.right == null) {// 创建临时链接predecessor.right = current;current = current.left;} else {// 临时链接已存在，访问节点predecessor.right = null; // 移除临时链接result.add(current.val);current = current.right;}}}return result;}
}莫里斯遍历的优点是它不需要额外的空间（除了递归调用栈的空间），但是它修改了树的结构，因此在遍历结束后需要恢复原始结构。此外，莫里斯遍历在处理只有一个子节点的节点时，会访问两次，这在某些情况下可能不是期望的行为。
