二叉树的中序遍历：左、根、右
根夹在左右中间：写下它时，左子树已经全部出现，右子树还一个没有。BST 的中序因此天然有序。
中序 = 左子树 → 根 → 右子树。递归按这三行直译。迭代把隐式调用栈换成显式栈：cur 一路向左入栈，走到空就弹出栈顶访问——此时它的左子树已经结束——再转向右孩子。时间 O(n)，空间 O(h)。
这是 LeetCode 94. Binary Tree Inorder Traversal。大白话：给你一棵二叉树的根节点，按「左子树、根、右子树」的顺序把节点值收进数组返回。「左」「右」指整棵子树，不是只指孩子那一个节点。空节点不是要打印的值，是递归的停手处。
本页主例是根为 1、左孩子 2、右孩子 3 的小树。中序必须先走完 2 的整棵左子树（它是叶子，左右都空），写下 2，再写下根 1，最后写下 3，序列是 [2, 1, 3]。根 1 出现在 2 之后、3 之前，这正是「中」的含义。
对二叉搜索树做中序，得到的就是递增序列——左子树所有值先出来且都小于根，再输出根，再输出右子树且都大于根。这是中序最重要的推论，也是验证 BST 的直接依据。迭代版「一路向左、出栈访问」是面试高频模板，它不是另一种定义，只是把递归的调用栈改成你自己维护。
中序的契约：根在中间
每个节点都要做且只做三件事：处理自己、走完左子树、走完右子树。三种遍历的差别，只是「处理自己」插在另外两件之间的哪个缝里。中序把处理放在左右之间，所以一根节点被写下时，它左边的整棵子树已经全部出现，右边还一个没有。
主例用手走一遍。进入 1，先不写，往左走到 2。2 左边空，写下 2，2 右边空，回到 1。1 的左边结束，写下 1，转向 3。3 左边空，写下 3。序列是 [2, 1, 3]。每一个数字被写下时，它的左子树都已经全部出现：2 的左子树空，1 的左子树只有 2。
若这棵树是 BST——左 2 小于根 1 小于右 3——中序 [2, 1, 3] 恰好升序。换一棵乱序的树，中序仍然是左、根、右，只是不再有序。有序性来自 BST 的约束，不是中序定义本身。空树返回空数组；单节点只写下自己。
有序性BST 中序必有序：左子树全部小于根，右子树全部大于根，递归地，整段序列严格递增。验证 BST 可以扫中序、记前一个值。
迭代：一路向左，出栈访问
递归能跑起来，是因为函数调用自己会形成一条调用栈：当前节点还没走完，就被压在栈里，等左子树回来再写自己。非递归缺的就是这份记忆。显式栈的工作是：左子树还没走完的根先挂起，左子树结束才拿出来访问，访问完转向右孩子。
模板是两个循环套在一起。外循环条件是 cur 非空或栈非空——还有人没走完。内循环：cur 非空时，把 cur 入栈，cur = cur.Left，一路向左压到头。内循环结束说明当前这条左链走空了，弹出栈顶：它要么没有左孩子，要么左孩子已被处理，现在轮到「根」的位置，写入它的值，再令 cur = 它的 Right，对右孩子重复「一路向左」。
主例从根 1 开始。内循环把 1、再把 2 压进栈，2 的左是空，内循环停。弹出 2，写入 2，2 没有右孩子，cur 变空。外循环继续，弹出 1，写入 1，cur 转向 3。3 入栈，左空，弹出并写入 3。序列仍是 [2, 1, 3]。栈里同时存在的，是「已经看见、但左子树刚结束、自己还没写」的人，和递归时挂起的那些帧是同一批责任。
为什么出栈才访问？因为入栈时左子树还没走完，现在写根就变成了前序。出栈那一刻，左子树已经全部结束，正好卡在中序约定的那条缝里。时间仍是每个节点入栈出栈各一次，O(n)；栈最深是树高 O(h)。
Go：递归与迭代
func inorderTraversal(root *TreeNode) []int {res := []int{}var dfs func(*TreeNode)dfs = func(n *TreeNode) {if n == nil { return }dfs(n.Left)res = append(res, n.Val)dfs(n.Right)}dfs(root)return res}// 迭代版func inorderIter(root *TreeNode) []int {res, stack, cur := []int{}, []*TreeNode{}, rootfor cur != nil || len(stack) > 0 {for cur != nil {stack = append(stack, cur)cur = cur.Left}cur = stack[len(stack)-1]stack = stack[:len(stack)-1]res = append(res, cur.Val)cur = cur.Right}return res}
1递归与定义同构：先走完左子树，再写入根，再走右子树。空节点直接返回。
2迭代外循环 cur 非空或栈非空，表示还有节点没处理完。
3内循环一路向左入栈：根先挂起，左子树还没走完，现在绝不能写。
4出栈那一刻左子树已经结束，写入栈顶的值，这才是中序的「根」。
5转向右孩子，对右子树重复同一套「向左入栈、出栈访问」。
总结
中序把根夹在左右中间；迭代用「向左入栈、出栈访问、转向右」模拟那条调用栈。
- 写下根时，左子树已经全部出现，右子树还一个没有。BST 加上这条约定，中序就是升序。
- 迭代不是另一种遍历定义。入栈时左子树未完，出栈才轮到根，再把 cur 换成右孩子。
- 递归与迭代都是每个节点进出一次，时间 O(n)，额外空间是树高。