Accepted, C++ iterative DFS with stack method


  • 0
    R
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<string> binaryTreePaths(TreeNode* root) {
            //dfs, but use a vector to store the temp result 
            //and print this vector everytime when leaf is hit
            if(!root) return {};
            stack<TreeNode*> s;
            s.push(root);
            
            vector<string> result;
            vector<TreeNode*> rc;
            while(!s.empty())
            {
                TreeNode* n = s.top();
     
                if(rc.empty() ||(rc.back())->right == n || (rc.back())->left == n)
                {
                    rc.push_back(n);
                    if(!n->left && !n->right)
                    {
                        //this is leaf
                        //determine if it is the time to add the result
    
                        //add to the result
                        string rs;
                        for(auto node : rc)
                        {
                            rs += to_string(node->val);
                            if(node != rc.back())
                                rs += "->";
                        }
                        result.push_back(rs);
                    }
                    s.pop();
                    if(n->left) s.push(n->left);
                    if(n->right) s.push(n->right);
                }
                else
                {
                    rc.pop_back();
                }
            }
            return result;
        }
    };```

Log in to reply
 

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