二叉树的遍历图解例题方法
二叉树（Binary Tree）是一种非常重要的数据结构，他的特殊性质决定了它在计算机科学中的广泛应用。在进行二叉树的操作中，遍历（Traversal）是最基本的一种操作。因此，本文将从多个角度分析二叉树的遍历图解例题方法。
一、遍历的定义和分类
遍历是指从某个固定的位置出发，按照某种次序依次访问树中所有节点，使每个节点仅被访问一次。在二叉树中，遍历可以分为三种方式：前序遍历（Preorder Traversal）、中序遍历（Inorder Traversal）和后序遍历（Postorder Traversal）。具体定义如下：
前序遍历：先遍历根结点，然后遍历左子树，最后遍历右子树。
中序遍历：先遍历左子树，然后遍历根结点，最后遍历右子树。
后序遍历：先遍历左子树，然后遍历右子树，最后遍历根结点。
二、递归算法
递归是最基本、最简单的算法。在递归算法中，我们通过不断地调用函数本身来解决问题。二叉树的遍历可以通过递归方式实现，代码如下：
前序遍历：
void preorderTraversal(TreeNode* root) {
if(root == NULL) {
return;
}
cout << root->val << endl; // 访问根节点
preorderTraversal(root->left); // 遍历左子树
preorderTraversal(root->right); // 遍历右子树
}
中序遍历：
void inorderTraversal(TreeNode* root) {
if(root == NULL) {
return;
}
inorderTraversal(root->left); // 遍历左子树
cout << root->val << endl; // 访问根节点
inorderTraversal(root->right); // 遍历右子树
}
后序遍历：
void postorderTraversal(TreeNode* root) {
if(root == NULL) {
return;
}
postorderTraversal(root->left); // 遍历左子树
postorderTraversal(root->right); // 遍历右子树
cout << root->val << endl; // 访问根节点
}
三、迭代算法
递归算法是最自然的二叉树遍历算法，但是它的缺点是递归调用函数占用大量的空间。迭代算法是一种优化的算法，它不需要递归。基本思想是使用一个栈来保存已经访问过的结点。以前序遍历为例，具体代码如下：
vector
vector
stack
if(root != NULL) {
s.push(root); // 根节点入栈
}
while(!s.empty()) {
TreeNode* node = s.top();
s.pop();
result.push_back(node->val); // 访问根节点
if(node->right != NULL) {
s.push(node->right); // 右子树入栈
}
if(node->left != NULL) {
s.push(node->left); // 左子树入栈
}
}
return result;
}
中序遍历和后序遍历的迭代算法也可以类似实现。
四、例题解析
以题目LeetCode 144. Binary Tree Preorder Traversal为例，给出前序遍历的例题解析。
题目描述：
给定一个二叉树，返回它的前序遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,2,3]
题目分析：
这道题用递归算法非常简单，这里主要是介绍一下使用迭代算法的解法。使用栈存储访问过的结点，优先访问右子树结点，再访问左子树结点。代码如下：
vector
vector
stack
if(root != NULL) {
s.push(root); // 根节点入栈
}
while(!s.empty()) {
TreeNode* node = s.top();
s.pop();
result.push_back(node->val); // 访问根节点
if(node->right != NULL) {
s.push(node->right); // 右子树入栈
}
if(node->left != NULL) {
s.push(node->left); // 左子树入栈
}
}
return result;
}
