二叉树的遍历图解例题方法

二叉树（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 preorderTraversal(TreeNode* root) {

vector result;

stack s;

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 preorderTraversal(TreeNode* root) {

vector result;

stack s;

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;

}