Solution by postorder traversal


  • -1
    F

    class Solution {
    public:
    string itos(int n){
    stringstream ss;
    ss<<n;
    string str;
    ss>>str;
    return str;
    }
    string convert(deque<TreeNode*> &q){
    if(q.empty()) return "";
    string str;
    for(int i=0;i<q.size()-1;i++) str+=itos(q[i]->val)+"->";
    str+=itos(q.back()->val);
    return str;
    }
    vector<string> binaryTreePaths(TreeNode* root) {
    TreeNode* p=root;
    deque<TreeNode*> st;
    deque<bool> ft;
    vector<string> ret;
    while(p!=NULL||!st.empty()){
    while(p!=NULL){
    st.push_back(p);
    ft.push_back(true);
    p=p->left;
    }
    if(!st.empty()){
    p=st.back();
    bool f = ft.back();
    if(f){
    ft.pop_back();
    ft.push_back(false);
    p=p->right;
    }else{
    if(p->left==NULL&&p->right==NULL){
    string s=convert(st);
    ret.push_back(s);
    }
    st.pop_back();
    ft.pop_back();
    p=NULL;
    }
    }
    }
    return ret;
    }
    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.