二叉树的中序遍历94
题干
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
提示：
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
思路
这道题有2种思路。一是用递归做，二是用迭代维护一个栈。
讲递归之前，先讲讲二叉树。
二叉树有一个根节点和左右分支，通常我们用这样的结构体来定义二叉树类型。最好能够默写这个数据结构。
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
这里假设都已经理解了指针。所以，接下来我们讲一下中序是什么，中序是指二叉树的一种遍历顺序，左子树 → 根节点 → 右子树。递归函数会一直向左深入，直到最左节点，然后逐层返回。
想象你是一个图书管理员，需要整理一棵特殊的“书树”——每个节点是一本书，每本书可能左边有一本小书（左子节点），右边也有一本小书（右子节点）。你的任务是用“中序”方式清点所有书，规则是：对任何一本书，先清点它左边所有书，再清点它自己，最后清点它右边所有书。
现在，你站在最顶上的那本书（根节点）前，比如书名叫《1》。你记得规则：必须先清点它左边的所有书。但左边那本书（如果存在）自己也有左右小书，所以你不能直接跳过。于是你对自己说：“我先去处理左边那本书，用同样的规则：先清点它的左边，再清点它自己，最后清点它的右边。” 就这样，你一层一层地往左深入，直到遇到一本书没有左边小书了。
当走到一本没有左边小书的书时，规则说：它的左边已经没了（相当于清点完毕），那么现在就可以清点它自己了——你记下这本书的名字。然后，再去看它的右边小书，如果有，就用同样的方式处理那本右边小书（先左边、再自己、再右边）。等右边全部清点完，你才回到上一本书，继续刚才的步骤——上一本书此时左边全部处理完毕，于是清点它自己，再处理它的右边……
用这个规则处理示例树：
1
\
2
/
3
你站在《1》前，发现它没有左边书（左边是空的），那么规则说：左边处理完了（实际上什么也没做），现在就可以清点《1》自己——你记下“1”。然后你需要处理它的右边书《2》。你走到《2》前，规则要求：先处理它的左边书。左边有《3》，所以你走到《3》前。对于《3》，它没有左边书，所以直接清点《3》自己（记下“3”），然后它右边也没有书，于是《3》处理完毕。你回到《2》，此时《2》的左边已经处理完，你就清点《2》自己（记下“2”），然后处理它的右边（空的）。最后回到《1》，整个任务完成，清点顺序是：1，3，2。完美符合中序：左、根、右（但注意《1》的左为空，所以先根《1》，然后去右子树，在右子树中又是左《3》再根《2》）。
用递归就可以实现这个过程。
在示例 root = [1, null, 2, 3] 中，整棵树的根节点是 1。
在递归遍历过程中，每个递归函数调用都有一个当前根节点（即传入的 root 参数）。我们来标记一下前面模拟的每一步中，当前根节点是谁： 递归调用过程（带当前节点标注）
-
第一次调用：inorder(1, res)
当前根节点：1
执行：先递归左子树 → 调用 inorder(1->left, res)，即 inorder(nullptr, res)。
-
第二次调用：inorder(nullptr, res)
当前根节点：nullptr
执行：触发 if (!root) return;，立即返回。
-
返回第一次调用：继续执行 res.push_back(1)
此时当前根节点仍是 1（因为刚刚从子调用返回，当前函数是 inorder(1)）
记录 1 到结果集。
-
然后调用 inorder(1->right, res)，即 inorder(2, res)
当前根节点变为 2。
-
进入 inorder(2, res)
当前根节点：2
先递归左子树：调用 inorder(2->left, res)，即 inorder(3, res)。
-
进入 inorder(3, res)
当前根节点：3
先递归左子树：inorder(3->left, res) → inorder(nullptr, res)，立即返回。
然后记录 3（当前根节点为 3）到结果集。
再递归右子树：inorder(3->right, res) → inorder(nullptr, res)，返回。
函数结束，返回上一级 。
-
返回 inorder(2, res)（此时当前根节点回到 2）
继续执行：记录 2 到结果集。
再递归右子树：inorder(2->right, res) → inorder(nullptr, res)，返回。
函数结束，返回上一级。
-
返回 inorder(1, res)（当前根节点回到 1）
函数结束，遍历完成。
这个过程中，管理员其实是靠记忆（系统自动的“调用栈”）记住自己处理到哪一步了：走到左边深处时，脑子里还记着“等会儿要回来处理这本书”。这种记忆是自动的，不用自己操心。
而迭代方法需要我们手动维护一个栈。
现在，管理员决定用便签纸来手动管理任务。每遇到一本暂时不能清点的书，就写一张便签压在桌上（入栈），等时机到了再拿出来处理。
具体操作流程是这样的：
-
从最上面的书（根节点）开始，管理员拿着一支笔，当前指着这本书（用 cur 表示当前指向的书）。
-
一直往左走，沿途压栈：只要当前指向的书不是空的，管理员就做两件事：
把这本书的书名写在一张便签上，压在桌子上的便签 堆最上面（入栈）。
然后拿起这本书左边的小书，继续往左走（cur = cur->left）。
这样一路向左，直到走到一本没有左边小书的书为止（此时 cur 指向空）。
-
弹出栈顶，清点它，然后转向右边：
当左边走到头（cur 为空），管理员就从便签堆最上面抽出一张便签（弹出栈顶），这张便签上记的就是当前需要清点的书。
清点这本书（记录它的值）。
然后，拿起这本书的右边小书（cur = cur->right），准备开始处理右边。
-
重复第2步和第3步：只要 cur 不为空或者便签堆里还有便签，就继续循环。因为右边小书也可能有自己的左边小书，所以又要重复“往左压栈”的过程。
这样，通过手动控制便签的压入和弹出，管理员就能按照“左-中-右”的顺序清点所有书，而不需要依靠自动记忆。
题解
递归：
// struct TreeNode {
// int val;
// TreeNode *left;
// TreeNode *right;
// TreeNode() : val(0), left(nullptr), right(nullptr) {}
// TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
// TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// };
class Solution {
public:
void inorder(TreeNode* root, vector<int>& res){
if(!root)return;
inorder(root->left,res);
res.push_back(root->val);
inorder(root->right,res);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
inorder(root,ans);
return ans;
}
};
迭代：
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> stk;
TreeNode* cur = root;
while(cur!=nullptr||!stk.empty()){
// 将左节点压入栈
while(cur!=nullptr){
stk.push(cur);
cur = cur->left;
}
// 左边的节点处理完了，这样就需要弹出栈顶节点并访问
cur = stk.top();
stk.pop();
ans.push_back(cur->val);
// 转向右子树，下一轮循环会处理它的左子树
cur = cur->right;
}
return ans;
}
};