【题干】
给定一个二叉树的根节点?root
?,返回?它的?中序?遍历?。
【思路】
由于题很简单,今天试试写多解,不然实在是太偷懒了。
怎么说呢,链表遍历毕竟还是太经典了,所以只是记录了一下关键思路,让我们来看代码吧。
【题解】
递归
class Solution {
public:
void inorder(TreeNode* root, vector<int>& ans) {
if (!root)
return;
inorder(root->left,ans);
ans.push_back(root->val);
inorder(root->right,ans);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
inorder(root, ans);
return ans;
}
};
迭代
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
TreeNode* cur =root;
vector<int> ans;
stack<TreeNode*> stk;
while(cur||!stk.empty()){
while(cur){
stk.push(cur);
cur=cur->left;
}
cur=stk.top();
stk.pop();
ans.push_back(cur->val);
cur=cur->right;
}
return ans;
}
};
着色
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
stack<pair<TreeNode*,int> > stk;
stk.push(make_pair(root,0));
while(!stk.empty()){
auto [node, color]=stk.top();
stk.pop();
if(node==nullptr)continue;
if(color==0){
stk.push(make_pair(node->right,0));
stk.push(make_pair(node,1));
stk.push(make_pair(node->left,0));
}else{
ans.push_back(node->val);
}
}
return ans;
}
};
Morris
class Solution {
public:
TreeNode* getPredecessor(TreeNode* root){
TreeNode* cur=root->left;
while(cur->right&&cur->right!=root) cur=cur->right;
return cur;
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
while(root){
if(root->left){
TreeNode* pre=getPredecessor(root);
if(!pre->right){
pre->right=root;
root=root->left;
}else{
ans.push_back(root->val);
root=root->right;
pre->right=nullptr;
}
}else{
ans.push_back(root->val);
root=root->right;
}
}
return ans;
}
};