力扣 94.二叉树的中序遍历(简单)_力扣94题

  （力扣上给出的难度是简单，但有半年没接触过类似的题了，感觉还是很陌生）

题目：
给定一个二叉树的根节点 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]

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

题解如下：（看了官方的题解做的）
首先：什么是中序遍历？

什么是二叉树的中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。

递归方法

class Solution {
public:
    void mid(TreeNode* root,vector<int>& res)//递归
    {
        if(root==NULL)//递归函数的出口
        {return;}
        mid(root->left,res);//递归节点左字数
        res.push_back(root->val);//把当前节点的值放到结果数组中
        mid(root->right,res);//递归节点右子树
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;//先定义一个储存答案的
        mid(root,res);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

C++中push_back函数使用方法：网站
迭代方法

二叉树的中序遍历因为要一直访问到左子树的最左边，所以需要一个指针变量帮助找到二叉树的最左边的节点。

迭代方法内存消耗少

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;//像递归一样，先定义一个储存结果的数组
        stack<TreeNode* > stk;//定义一个栈
        TreeNode *s = root;
        while(s != nullptr || !stk.empty())
        {
            while(s!=nullptr)//非空
            {
                stk.push(s);//将数值放到栈中去
                s = s->left;
            }
            //此时s为空，说明s上一个节点无左子树
            s = stk.top();
            stk.pop();
            res.push_back(s->val);//将放入栈的值取入答案数组
            s = s->right;//再进入右子树

        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

栈stack的常见用法：网站

快乐进步每一天~