LeetCode 热题 100_二叉树的中序遍历（36_94_简单_C++）（二叉树；递归（中序遍历）；迭代）

题目描述：

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

输入输出样例：

示例 1：

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

示例 2：
输入：root = []
输出：[]

示例 3：
输入：root = [1]
输出：[1]

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

题解：

解题思路：

思路一（递归）：

1、中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树。正好符合递归的过程。（中序遍历从宏观上来看，其实就是从左往右看到的结点挨个输出）

2、复杂度分析：
① 时间复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
② 空间复杂度：O(n)。空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。

思路二（迭代）：

1、我们通过一个栈来模拟方法一中函数入栈的过程。
官方题解链接（有图，感觉很不错：注意体会结点的遍历过程）

2、复杂度分析
① 时间复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
② 空间复杂度：O(n)。空间复杂度取决于栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。

代码实现

代码实现（思路一（递归））：

void inorder(TreeNode* root,vector<int> &res) {
	//递归出口
    if (root==nullptr) return ;
    inorder(root->left,res);
    res.emplace_back(root->val);
    inorder(root->right,res);
}

//方法一：递归方式实现中序遍历
vector<int> inorderTraversal1(TreeNode* root){
    vector<int> res;
    inorder(root,res);
    return res;
} 

代码实现（思路二（迭代））：

//方法二：迭代实现中序遍历
vector<int> inorderTraversal2(TreeNode* root){
	//存储中序遍历结果
    vector<int> res;
    stack <TreeNode *> stk;
    while (root!=nullptr||!stk.empty())
    {
        //将左子树入栈
        while (root!=nullptr)
        {
            stk.push(root);
            root=root->left;
        }

        //如果没有左侧结点则当前结点为输出结点（出栈结点）
        root=stk.top();
        stk.pop();
        res.push_back(root->val);
        //遍历右子树
        root=root->right;
        
    }
    return res;
}

以思路二为例进行调试

#include <iostream>
#include <vector>
#include <queue>
#include<stack>
using namespace std;
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){}
};

//通过数组创建二叉树，-1代表nullptr 
TreeNode* buildTree(const vector<int>& nums) {
    if (nums.empty()) return nullptr;

    TreeNode* root = new TreeNode(nums[0]);
    //使用队列一层一层的创建二叉树
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;

    while (i < nums.size()) {
        //插入最先入队的结点的孩子结点
        TreeNode* current = q.front();
        q.pop();
        //左孩子不为空则创建结点，连接到二叉树中，插入队列
        if (i < nums.size() && nums[i] != -1) {
            current->left = new TreeNode(nums[i]);
            q.push(current->left);
        }
        i++;
        //右孩子不为空则创建结点，连接到二叉树中，插入队列
        if (i < nums.size() && nums[i] != -1) {
            current->right = new TreeNode(nums[i]);
            q.push(current->right);
        }
        i++;
    }

    return root;
}

//方法二：迭代当时实现中序遍历
vector<int> inorderTraversal2(TreeNode* root){
    vector<int> res;
    stack <TreeNode *> stk;
    while (root!=nullptr||!stk.empty())
    {
        //将左子树入栈
        while (root!=nullptr)
        {
            stk.push(root);
            root=root->left;
        }

        //如果没有左侧结点则当前结点为输出结点（出栈结点）
        root=stk.top();
        stk.pop();
        res.push_back(root->val);
        //遍历右子树
        root=root->right;
        
    }
    return res;
}

int main() {
// 使用 -1 来表示空节点
vector nums = {1, 2, 3, 4, 5, -1, 6};

TreeNode *root = buildTree(nums);   

// 中序遍历输出构造的二叉树
vector<int> ans= inorderTest(root);  // 输出: 1 2 4 5 3 6
for (const auto &i : ans)
{
    cout<<i<<"  ";
}
return 0;

}

LeetCode 热题 100_二叉树的中序遍历（36_94)原题链接
欢迎大家和我沟通交流(✿◠‿◠)