# 二叉树的中序遍历

​ 大一 -> 大二暑期算法作业

分站已经上线简约风算法作业集合(也可以选择阅读模式

# 看到题目的感想

​ 被离散数学折磨之后看见树就会想到离散数学,虽然学习离散数学的时候老师教过中序遍历,但是看到这个题的时候还是没有想起来中序遍历是个啥,索性就去搜索了一下(快进到被老师打死)。

​ 附上百度百科链接:

中序遍历:https://baike.baidu.com/item/ 中序遍历

# 题目描述

给定一个二叉树的根节点 root ,返回它的 中序 遍历。

示例 1:

img

输入:root = [1,null,2,3]
输出:[1,3,2]

示例 2:

输入:root = []
输出:[]

示例 3:

输入:root = [1]
输出:[1]

示例 4:

img

输入:root = [1,2]
输出:[2,1]

示例 5:

img

输入:root = [1,null,2]
输出:[1,2]

提示:

树中节点数目在范围 [0, 100] 内
- 100 <= Node.val <= 100

进阶:递归算法很简单,你可以通过迭代算法完成吗?

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-tree-inorder-traversal

# 题目解答

​ (**ps:** 由于做题时采用的是执行代码,并未提交,提交结果均为后来补上,所以时间均为两天前)

# 1. 递归算法

利用递归的思想解题也是老朋友了,在之前的算法题里面有过接触,所以并不是很难理解。

# (1)解题思路

​ 在解题的时候,了解到了一个名叫 vector 的东西,可以理解为 C++ 和 Java 中的一种动态数组。记得第一次听到这个名词的时候还是在翁恺老师的《C 语言程序设计》这门课上听到的,想想还真是怀念。(跑远了

附上一些链接(配合梯子一起食用):

vector:内存在堆上

注意:vector 每添加一次都会把之前的全复制一遍,所以效率并不高。

1) https://docs.microsoft.com/zh-cn/cpp/standard-library/vector-class?view=msvc-160 来源:Microsoft C++、C 和汇编程序文档

2) https://docs.oracle.com/en/java/javase/16/docs/api/jdk.incubator.vector/jdk/incubator/vector/package-summary.html 来源:Java 官方文档里的包(纯英文比较难顶

3) https://baike.baidu.com/item/Vector/3330482 来源:百度百科

4) https://www.w3cschool.cn/cpp/cpp-i6da2pq0.html 来源:某不知名 C++ 教程

《C 语言程序设计》:https://www.icourse163.org/learn/ZJU-9001?tid=9001#/learn/announce 来源:中国大学 MOOC

​ 本题可以通过递归思想对给出的二叉树的左子树、根节点、右子树依次进行遍历(中序遍历),并将各个数据存放在设置好的 vector中(由于 vector 是动态分配内存的,所以比用担心大小会不够用),最后即可得到该二叉树的中序遍历。

# (2)代码

​ 解题代码如下(配合题目链接食用):

# C++

有一种比较好用的 C++ 容器,比 vector 好用,只是不能自增。(本题未使用)

array:内存在栈上

array: http://c.biancheng.net/view/6688.html 来源:C 语言中文网

array: https://www.bilibili.com/video/BV18b4y1X7EB?from=search&seid=11718690349134275715 来源:哔哩哔哩(是一个油管的小哥哥,讲的很棒,圈粉了)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* Definition for a binary tree node.
* 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出去
return;
}
inorder(root->left, res); // 递归遍历左子树
res.push_back(root->val); // 将该节点的值增加在动态数组末尾
inorder(root->right, res); // 递归遍历右子树
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res; // 新建一个int类型的vector,用来存放遍历结果
inorder(root, res); // 从根节点root开始遍历,依次放入值
return res; // 返回遍历结果
}
};
  • image-20210827092120481.png
# Java

List & ArrayList 是 Java 中的一种列表。

List & ArrayList:https://www.jianshu.com/p/25aa92f8d681 来源:简书

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/

class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>(); // 新建Integer的List来存放数值
inorder(root, res); // 从根节点root开始遍历,依次将数值放入
return res; // 返回遍历结果
}

public void inorder(TreeNode root, List<Integer> res) {
if (root == null) { // 如果碰到空节点,说明该部分遍历已完成,return出去
return;
}
inorder(root.left, res); // 递归遍历左子树
res.add(root.val); // 将该节点的值增加在末尾
inorder(root.right, res); // 递归遍历右子树
}
}

image-20210827092151479.png

# C(来自题解)

(C 语言中的动态数组不会玩,于是把题解拿过来)

C 语言动态数组 https://www.runoob.com/w3cnote/c-dynamic-array.html 来源:菜鸟教程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/


/**
* Note: The returned array must be malloced, assume caller calls free().
*/

void inorder(struct TreeNode* root, int* res, int* resSize) {
if (!root) {
return;
}
inorder(root->left, res, resSize);
res[(*resSize)++] = root->val;
inorder(root->right, res, resSize);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
int* res = malloc(sizeof(int) * 501);
*returnSize = 0;
inorder(root, res, returnSize);
return res;
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

# (3)总结

​ 利用递归思想来解题还是比较舒服的,也很好用,适合我这种菜鸡。

# 2. 迭代算法

关于迭代算法的基本思想:

迭代算法 https://www.cnblogs.com/cs-whut/p/11024564.html 来源:博客园

​ 迭代算法之前没有接触过,上手有点看不懂。

# (1)解题思路

​ 通过迭代 + 栈模型来清楚的展现解题流程(题解中有动画展示,配合食用比较好理解)。

# (2)代码

​ 解题代码如下(配合题目链接食用):

# C++

C++ 的栈:

stack http://c.biancheng.net/view/478.html 来源:C 语言中文网

stack https://www.apiref.com/cpp-zh/cpp/container/stack.html 来源:C++ 文档

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* Definition for a binary tree node.
* 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:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res; // 新建一个int类型的vector,用来存放遍历结果
stack<TreeNode*> stk; // 新建栈
while (root != nullptr || !stk.empty()) { // 节点有数值 或 栈不为空
while (root != nullptr) { // 当节点有值时
stk.push(root); // 数据入栈
root = root->left; // 访问左子树
}
root = stk.top(); // 找到栈顶数据的节点
// top():返回一个栈顶元素的引用,类型为 T&。如果栈为空,返回值未定义。
stk.pop();
// pop():弹出栈顶元素。
res.push_back(root->val); // 在vector末尾添加当前节点数据
root = root->right; // 访问右子树
}
return res; // 返回结果
}
};

image-20210827092218700.png

# Java

Java 的栈:

Deque: https://www.jianshu.com/p/d78a7c982edb 来源:简书

stack:**

(1) https://www.javatpoint.com/java-stack 来源:某 Java 文档

(2) https://blog.csdn.net/YQYnsmile/article/details/78457539 来源:屑 C 某某 N

(3) https://docs.oracle.com/en/java/javase/16/docs/api/java.base/java/util/Stack.html 来源:某全英文 Java 文档

Deque 可以作为堆栈(LIFO 后进先出),此接口优于传统 Stack 类的使用。

Stack 和 Deque 方法的比较

栈方法 等效 Deque 方法
push(e) addFirst(e)
pop() removeFirst()
peek() peekFirst()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/

class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>(); // 新建List来保存数据
Deque<TreeNode> stk = new LinkedList<TreeNode>(); // 新建栈
while (root != null || !stk.isEmpty()) { // 节点有数值 或 栈不为空
while (root != null) { // 节点有数值时
stk.push(root); // 将数据放入栈
root = root.left; // 访问左子树
}
root = stk.pop(); // pop():弹出栈顶元素。
res.add(root.val); // 在List末尾添加当前节点数据
root = root.right; // 访问右子树
}
return res; // 返回结果
}
}

image-20210827092339328.png

# C(来自题解)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/


/**
* Note: The returned array must be malloced, assume caller calls free().
*/

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
*returnSize = 0;
int* res = malloc(sizeof(int) * 501);
struct TreeNode** stk = malloc(sizeof(struct TreeNode*) * 501);
int top = 0;
while (root != NULL || top > 0) {
while (root != NULL) {
stk[top++] = root;
root = root->left;
}
root = stk[--top];
res[(*returnSize)++] = root->val;
root = root->right;
}
return res;
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

# (3)总结

​ 利用迭代算法来解题的思想还没有怎么接触过没上手感觉比较难。(还是递归香 确信

# 3.Morris 中序遍历(来自题解)

​ 这个就是真的闻所未闻了,看了题解,决定搬过来

# (1)思路与算法

  1. Morris 遍历算法是另一种遍历二叉树的方法,它能将非递归的中序遍历空间复杂度降为 O (1) O (1)。

    Morris 遍历算法整体步骤如下(假设当前遍历到的节点为 xx):

  2. 如果 xx 无左孩子,先将 xx 的值加入答案数组,再访问 xx 的右孩子,即 x = x . right。
    如果 xx 有左孩子,则找到 xx 左子树上最右的节点(即左子树中序遍历的最后一个节点,xx 在中序遍历中的前驱节点),我们记为 predecessor。根据 predecessor 的右孩子是否为空,进行如下操作。

    • 如果 predecessor 的右孩子为空,则将其右孩子指向 xx,然后访问 xx 的左孩子,即 x = x . left。
    • 如果 predecessor 的右孩子不为空,则此时其右孩子指向 xx,说明我们已经遍历完 xx 的左子树,我们将 predecessor 的右孩子置空,将 xx 的值加入答案数组,然后访问 xx 的右孩子,即 x = x . right。
  3. 重复上述操作,直至访问完整棵树。

    4. 其实整个过程我们就多做一步:假设当前遍历到的节点为 xx,将 xx 的左子树中最右边的节点的右孩子指向 xx,这样在左子树遍历完成后我们通过这个指向走回了 xx,且能通过这个指向知晓我们已经遍历完成了左子树,而不用再通过栈来维护,省去了栈的空间复杂度。

# (2)代码

题解链接: https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/ 来源:力扣

​ 不想搬运代码了,就给出了链接。Morris 中序遍历是题解中的第三种解法,题解带有动画教程,可以看看。

# (3)总结

​ 一种没听过的中序遍历算法,搬运题解来的。(主要还是太菜了没玩明白)

# 题目总结

​ 此次题目中,出现了递归算法、迭代算法、Morris 遍历算法三种解题思路。

​ 总的来说,还是递归较好理解,写起来难度稍微低一些;迭代算法初次了解,试了试水;Morris 遍历算法第一次见,还是看题解叭(还是人菜)。