二叉树的中序遍历图解例题

二叉树是一种常见的数据结构，在算法设计中有广泛的应用。其中，树的遍历是一种常见的问题。这里，我们将重点讨论二叉树的中序遍历。本文将从以下几个角度进行分析：什么是中序遍历，中序遍历的应用，中序遍历的实现以及如何通过图解例题理解中序遍历。

什么是中序遍历？

中序遍历是指按照左-> 根-> 右的顺序访问二叉树中的节点。我们从树的根节点开始访问，首先遍历左子树，再访问根节点，最后遍历右子树。中序遍历是二叉树遍历的一种常见形式，其输出结果与二叉搜索树的排序结果一致。

中序遍历的应用

中序遍历在二叉搜索树中，有很重要的应用。在二叉搜索树中，所有左节点的值都小于根节点，所有右节点的值都大于根节点。因此，二叉搜索树的中序遍历顺序即为从小到大的排序结果，这使得中序遍历在查找二叉搜索树的特定值时非常有用。

此外，中序遍历还有其他应用，例如在求解二叉树的路径和或者数的直径等问题中，我们常常需要先进行中序遍历，然后进行其他的计算。

中序遍历的实现

中序遍历可以通过递归和非递归两种方法进行实现。

1.递归实现

递归实现中序遍历最为简单。我们只需要使用递归函数依次遍历左节点，根节点和右节点即可。以下是使用递归实现中序遍历的代码：

```

void inorderTraversal(TreeNode* root, vector & res) {

if (root == nullptr) {

return;

}

inorderTraversal(root->left, res);

res.push_back(root->val);

inorderTraversal(root->right, res);

}

```

2.非递归实现

非递归实现中序遍历可以使用栈来辅助实现。我们将每个节点压入栈中，在每个pop操作的时候，将其值加入返回列表中，并继续压入其右子节点和左子节点。由于栈是后进先出的数据结构，因此我们将先访问左子树，直到遍历到最底层节点，然后访问根节点和右子树。以下是使用非递归实现中序遍历的代码：

```

vector inorderTraversal(TreeNode* root) {

vector res;

stack s;

TreeNode* curr = root;

while (curr != nullptr || !s.empty()) {

while (curr != nullptr) {

s.push(curr);

curr = curr->left;

}

curr = s.top();

s.pop();

res.push_back(curr->val);

curr = curr->right;

}

return res;

}

```

通过图解例题理解中序遍历

以下是一道经典的例题：给定一个二叉树，返回中序遍历该二叉树的结果。例如，给定二叉树 [1,null,2,3]，输出 [1,3,2]。

通过一张图示，我们可以更直观地理解中序遍历。如下，中序遍历二叉树，即按照从左到右的顺序遍历其所有节点：


通过节点遍历的顺序从左到右，我们得到了数组 [1,3,2]。这也正是题目的输出结果。