94.二叉树的中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例1：
1
\
2
/
3
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
题目来源：力扣（LeetCode）
迭代思路
能否写出：不能写出，需要参考思路
时间：40分钟
思路：使用了一个栈来辅助遍历。首先将当前节点及其左子节点依次入栈，直到当前节点为空。然后从栈中弹出一个节点，将其值加入结果列表，然后将当前节点指向弹出节点的右子节点，继续下一轮遍历。重复这个过程，直到栈为空且当前节点为空，遍历结束。返回结果列表即为中序遍历结果。
// 仅是我的思路代码，leetcode上大神更厉害 class Solution { public List<Integer> inorderTraversal(TreeNode root) { ArrayList<Integer> result = new ArrayList<>(); if (root == null) { return result; } Stack<TreeNode> stack = new Stack<>(); TreeNode temp = root; while (temp != null || !stack.isEmpty()) { while (temp != null) { stack.push(temp); temp = temp.left; } TreeNode node = stack.pop(); result.add(node.val); temp = node.right; } return result; } }
时间复杂度：O(n)
空间复杂度：O(n)
中序遍历迭代与先序遍历迭代 逻辑顺序
中序遍历的迭代实现与先序遍历的迭代实现在遍历顺序上有所不同。
在中序遍历迭代实现中，首先将当前节点及其左子节点依次入栈，直到当前节点为空。然后从栈中弹出一个节点，将其值加入结果列表，并将当前节点指向弹出节点的右子节点，继续下一轮遍历。这样可以保证在遍历过程中按照左根右的顺序访问节点，即先访问左子树，再访问根节点，最后访问右子树。
而在先序遍历迭代实现中，首先将根节点入栈，然后进入循环，从栈中弹出一个节点，将其值加入结果列表，然后依次将右子节点和左子节点入栈。这样可以保证在遍历过程中按照根左右的顺序访问节点，即先访问根节点，再访问左子树，最后访问右子树。
因此，中序遍历迭代实现和先序遍历迭代实现的栈操作顺序略有不同，导致遍历顺序也不同。
其他思路
递归：
class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); inorder(root, res); return res; } public void inorder(TreeNode root, List<Integer> res) { if (root == null) { return; } inorder(root.left, res); // 递归遍历左子树 res.add(root.val); // 访问当前节点 inorder(root.right, res); // 递归遍历右子树 } }
时间复杂度：O(n)
空间复杂度：O(n)
Morris 中序遍历
