# 二叉树的中序遍历

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

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

# 看到题目的感想

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

​ 附上百度百科链接：

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

# 题目描述

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

示例 1：

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

示例 2：

输入：root = []
输出：[]

示例 3：

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

示例 4：

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

示例 5：

输入：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 来源：哔哩哔哩（是一个油管的小哥哥，讲的很棒，圈粉了）

/**
 * 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; // 返回遍历结果
    }
};

• 

# Java

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

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

/**
 * 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); // 递归遍历右子树
    }
}

# C（来自题解）

（C 语言中的动态数组不会玩，于是把题解拿过来）

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

/**
 * 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++ 文档

/**
 * 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; // 返回结果
    }
};

# 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()

/**
 * 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; // 返回结果
    }
}

# C（来自题解）

/**
 * 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 遍历算法第一次见，还是看题解叭（还是人菜）。