本文主要是介绍【LeetCode刷题记录】简单篇-94-二叉树的中序遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题目描述】
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
【测试用例】
示例1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例2：
输入：root = [ ]
输出：[ ]
示例3：
输入：root = [1]
输出：[1]
【思路分析】
在二叉树的遍历中，最常用的两种办法，分别是递归法和迭代法，并且这两种方法的思路和代码都已经相对成熟了，换句话说就是几乎已经固定了。
法一：递归法
遍历二叉树有四种方法，前序遍历，中序遍历，后序遍历和层次遍历。除了层次遍历以外，前三种遍历方法用递归的方式实现的逻辑是相同的，都是①递归左子树，②递归右子树，③输出root三个步骤，区别仅仅在于三个步骤的顺序。对于前序遍历，根节点root先输出，所以是③①②；对于中序遍历，根节点root在中间输出，所以是①③②；对于后序遍历，根节点root最后输出，所以是①②③。
对于二叉树的题目，大部分都是在遍历的基础上进行操作，即①②两个递归的操作不变，而根据具体题目要求在③输出root的过程中实现具体细节。
法二：迭代法
在二叉树的中序遍历中，用迭代法需要借助栈这一数据结构。栈内存储的是访问过但没有输出的树节点，因为最先输出的是二叉树最左下的节点，而最先访问的是根节点，所以这时就需要先将根节点入栈。例如，根节点为1，左子树为2，右子树为3，最先访问的是根节点1，但是中序遍历最先输出的是2，所以这时就需要将1入栈，输出2，再将1出栈输出，最后输出3。这里只是一个最简单的例子，实际中二叉树不止两层。
循环的条件是当前访问节点cur不为空且栈stack不为空，因为cur不为空和stack不为空都说明还有没有输出的节点，所以都要进入循环。
刚才说到了最先输出的是二叉树最左下的节点，在这之前访问过的所有节点都要先入栈，所以只要当前访问节点cur有左孩子，就要将cur入栈，并且访问其左孩子(cur = cur->left)，直到cur为空为止。
上一步结束后cur为空，此时栈顶节点就是二叉树中最左下的节点，所以将栈顶节点出栈并赋值给cur，输出cur->val。
此时相当于输出了最左下的一个子树的左孩子(为空)，根节点(即上一步输出的cur->val)，那么下一步需要输出的就是右孩子，即cur=cur->right。这一步做完就会自动进入下轮循环，相当于将以cur->right作为根节点的子树再次进行中序遍历，以此类推，整个循环结束后就实现了整棵树的中序遍历。
【参考代码】
法一：C实现
#include <stdio.h>
#include <stdlib.h> //easy-94-二叉树的中序遍历
int inorder(struct TreeNode* root, int* res, int* returnSize);
int* inorderTraversal(struct TreeNode* root, int* returnSize);struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
};//法一：递归
int* inorderTraversal(struct TreeNode* root, int* returnSize) {int* res = (int*)malloc(sizeof(int) * 101);*returnSize = 0;inorder(root, res, returnSize);return res;
}void inorder(struct TreeNode* root, int* res, int* returnSize){if(NULL == root){return NULL;}inorder(root->left, res, returnSize);res[(*returnSize)++] = root->val;inorder(root->right, res, returnSize);
}法一：C++实现
#include <iostream>
#include <vector>
using namespace std;//easy-94-二叉树的中序遍历
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(struct TreeNode* root, vector<int>& res);vector<int> inorderTraversal(TreeNode* root);
}; //法一：递归
vector<int> Solution::inorderTraversal(TreeNode* root){vector<int> res;inorder(root, res);return res;
}void Solution::inorder(struct TreeNode* root, vector<int>& res){if(NULL == root){return;}inorder(root->left, res);res.push_back(root->val);inorder(root->right, res);
}法二：C实现
#include <stdio.h>
#include <stdlib.h> //easy-94-二叉树的中序遍历
int inorder(struct TreeNode* root, int* res, int* returnSize);
int* inorderTraversal(struct TreeNode* root, int* returnSize);struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
};//法二：迭代
int* inorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize = 0;int* res = (int*)malloc(sizeof(int) * 101);struct TreeNode* stack = (struct TreeNode*)malloc(sizeof(struct TreeNode) * 101);int top=-1;struct TreeNode* cur = root;while(cur!=NULL || top!=-1){while(cur!=NULL){stack[++top] = *cur;cur = cur->left; }cur = &stack[top--];res[(*returnSize)++] = cur->val;cur = cur->right; }return res;
}法二：C++实现
#include <iostream>
#include <vector>
#include <stack>
using namespace std;//easy-94-二叉树的中序遍历
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(struct TreeNode* root, vector<int>& res);vector<int> inorderTraversal(TreeNode* root);
}; //法二：迭代
vector<int> Solution::inorderTraversal(TreeNode* root){stack<struct TreeNode> stack;vector<int> res;struct TreeNode* cur = root;while(cur!=NULL || stack.size()!=0){while(cur!=NULL){stack.push(*cur);cur = cur->left;}cur = &stack.top();stack.pop();res.push_back(cur->val);cur = cur->right;}return res;
}
这篇关于【LeetCode刷题记录】简单篇-94-二叉树的中序遍历的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
