在这篇文章中，我们将深入探讨题目 "94. 二叉树的中序遍历" 的内涵与解题方法。这个问题引导我们遍历一棵二叉树，以中序的方式呈现节点顺序，从而形成一个整数数组，将这个中序遍历结果呈现出来。
解构题意
题目要求我们给定一棵二叉树的根节点 root，并将这棵二叉树按照中序遍历的顺序转化为一个整数数组，最终返回这个中序遍历结果。
思路解析
中序遍历的核心思想在于，从根节点出发，首先递归地遍历其左子树，然后访问当前节点，最后再递归地遍历右子树。这个过程可以确保所有节点按照中序排列被访问。
下面是具体的步骤：
若当前节点为空，直接返回。
递归遍历当前节点的左子树，将左子树的节点按中序遍历的顺序添加到结果数组中。
将当前节点的值添加到结果数组中，代表访问当前节点。
递归遍历当前节点的右子树，将右子树的节点按中序遍历的顺序添加到结果数组中。
这样，最终结果数组中就存储了二叉树的中序遍历结果。
题目解析
以下是使用递归方法实现中序遍历的题解：
#include <vector>
// 二叉树节点的定义
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
std::vector<int> inorderTraversal(TreeNode* root) {
std::vector<int> result;
inorderTraversalRecursive(root, result);
return result;
}
private:
void inorderTraversalRecursive(TreeNode* root, std::vector<int>& result) {
if (root == nullptr) {
return;
}
// 遍历左子树
inorderTraversalRecursive(root->left, result);
// 访问当前节点
result.push_back(root->val);
// 遍历右子树
inorderTraversalRecursive(root->right, result);
}
};
实例剖析
假设我们有以下二叉树：
1
\
2
/
3
调用 inorderTraversal(root) 将会返回 [1, 3, 2]，这就是中序遍历的结果。
小结
透过深入分析中序遍历的思路，我们能够更好地领略这种遍历方式在二叉树上的工作方式。中序遍历是解决涉及二叉树问题时常用的基本方法，通过掌握其原理与实现，能够更深刻地理解二叉树的结构和算法。
