牛客网
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
vectorv1;
vectorv2;
vectorv3;
TreeNode* fistOr(TreeNode* r){
if(r!=nullptr){
v1.push_back(r->val);
fistOr(r->left);
fistOr(r->right);
}
return nullptr;
}
TreeNode* midOr(TreeNode* r){
if(r!=nullptr){
midOr(r->left);
v2.push_back(r->val);
midOr(r->right);
}
return nullptr;
}
TreeNode* backOr(TreeNode* r){
if(r!=nullptr){
backOr(r->left);
backOr(r->right);
v3.push_back(r->val);
}
return nullptr;
}
vector> threeOrders(TreeNode* root) {
fistOr(root);
midOr(root);
backOr(root);
return {move(v1),move(v2),move(v3)};
}
};
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
#define debug(x) cout
class Solution {
public:
vectorv1;
vectorv2;
vectorv3;
bool fistOr(TreeNode* r){
stackst;
if(r!=nullptr){
st.push(r);
}
while(!st.empty()){
auto t = st.top();
v1.push_back(t->val);
st.pop();
if( t->right!=nullptr ){
st.push(t->right);
}
if( t->left!=nullptr ){
st.push(t->left);
}
}
return true;
}
bool midOr(TreeNode* r){
stackst;
if( r!=nullptr ){
st.push(r);
auto tp = r;
while(tp->left != nullptr){
st.push(tp->left);
tp = tp->left;
}
}
while(!st.empty()){
auto tp = st.top();
st.pop();
v2.push_back(tp->val);
if( tp->right!=nullptr ){
tp = tp->right;
st.push(tp);
while(tp->left != nullptr){
st.push(tp->left);
tp = tp->left;
}
}
}
return true;
}
bool backOr(TreeNode* r){
stackst;
if( r!=nullptr ){
st.push(r);
auto tp = r;
while(tp->left != nullptr){
st.push(tp->left);
tp = tp->left;
}
}
TreeNode* lasto = nullptr;
while( !st.empty()){
auto tp = st.top();
//debug(tp->val)
tp = st.top();
//debug(00)
//debug(st.size())
if( tp->right == nullptr || tp->right == lasto ){
v3.push_back(tp->val);
//debug(111)
st.pop();
lasto = tp;
}
else{
tp = tp->right;
st.push(tp);
//debug(222)
while(tp->left != nullptr){
st.push(tp->left);
tp = tp->left;
}
}
}
return true;
}
vector> threeOrders(TreeNode* root) {
fistOr(root);
midOr(root);
backOr(root);
return {move(v1),move(v2),move(v3)};
}
};
LeetCode题解