给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3] 输出：[1,3,2]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
提示：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 10
代码：中序用递归来实现
class Solution {
public:
void inorder(TreeNode *root,vector<int>& res){
if(!root){
return;
}
inorder(root->left,res);
res.push_back(root->val);
inorder(root->right,res);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
inorder(root,res);
return res;
}
};
前序迭代版：用栈来实现
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode *> s;
s.push(root);
while(!s.empty()){
TreeNode *tmp = s.top();
s.pop();
if(!tmp) continue;
res.push_back(tmp->val);
s.push(tmp->right);
s.push(tmp->left);
}
return res;
}
};
前序遍历递归版：
class Solution {
public:
void frontorder(TreeNode *root,vector<int>& res)
{
if(!root)return;
res.push_back(root->val);
frontorder(root->left,res);
frontorder(root->right,res);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
frontorder(root,res);
return res;
}
};
后序递归版：
class Solution {
public:
void beheadorder(TreeNode *root,vector<int>& res)
{
if(!root) return;
beheadorder(root->left,res);
beheadorder(root->right,res);
res.push_back(root->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
beheadorder(root,res);
return res;
}
};