😄😊😆😃😄😊😆😃
开始cpp刷题之旅。
依旧是追求耗时0s的一天。
94. 二叉树的中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
思路：这个题目是二叉树的题目，做之前得先了解下二叉树的前序、中序、后序遍历的几种区别。
先序遍历：根->左->右
中序遍历：左->根->右
后序遍历：左->右->根
也就是说他这个先、中、后都是按照根节点处的位置来判断的，左子树始终在右子树之前。
关于遍历的具体实现步骤，看一个应该也就知道剩下其它的了。
本文的题目虽然是中序排序，但是理解后前序排序和后续排序也好做了。
中序遍历：
如果当前节点的左子树非空，则递归遍历左子树。
访问当前节点。
如果当前节点的右子树非空，则递归遍历右子树。
解法一：递归
整个排序是一层一层找下去的，思想中就带有递归。因此，最容易想到的应该就是递归。
class Solution {
public:
vector<int> results;
vector<int> inorderTraversal(TreeNode* root) {
traverse(root);
return results;
}
void traverse(TreeNode* node){
if(node==NULL) return;
traverse(node->left); //左节点
results.push_back(node->val); //根节点
traverse(node->right); //右节点
}
};
看一下提交记录：
OK, perfect。
解法二：迭代法
迭代法通过创建一个栈来实现。
先推入根节点，然后遍历左子树，一一推入栈中，当左子树遍历完后，将栈顶的值推入res中，并且删除栈顶值。这里还要判断栈顶的值有没有右节点，如果有的话将右节点推入栈中（栈先入后出）。再将右节点作为栈顶推入res中。这样迭代下去就可以实现对二叉树的中序排序。
class Solution {
public:
vector<int> results;
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> s; //创建一个栈
TreeNode* cur=root;
while(cur || !s.empty()){
//节点不为空时或者栈不为空时
//遍历左子树到底
while(cur){
s.push(cur); //入栈
cur=cur->left;
}
//cur为空，说明到了左子树的最下面，这时出栈
TreeNode* top = s.top();
results.push_back(top->val); //推栈顶的值
s.pop(); //出栈
//右子树
if(top->right )cur = top->right;
}
return results;
}
};
看一下提交记录：
OK， perfect。
😄😄😄😄😄😄😄😄
