C++: BFS solution, 4ms


  • 0
    X

    The most popular and well-known solution for this problem is using DFS.

    But what if we want to use BFS to solve this problem?

    My basic idea is using a vector to store the previous path, and using pair{int, TreeNode*} to bind the index of path in that vector with the node.

    class Solution {
    public:
        vector<string> binaryTreePaths(TreeNode* root) {
            queue<pair<int, TreeNode*>> q;
            vector<string> path;
            vector<string> res;
            path.push_back("");
            if(!root) return res;
            q.push({0, root});
            while(!q.empty()){
                auto p = q.front();
                q.pop();
                string s = path[p.first];
                s = s==""? to_string(p.second->val) : s + "->" + to_string(p.second->val);
                if(!p.second->left && !p.second->right) res.push_back(s);
                else{
                    path.push_back(s);
                    if(p.second->left) q.push({path.size()-1, p.second->left});
                    if(p.second->right) q.push({path.size()-1, p.second->right});
                }
            }
            return res;
        }
    };

  • 0
    S

    why not just define a node
    { string str_so_far;
    TreeNode * node;
    }


  • 0
    X

    @starmdrog, that's a good idea, and I really like it :)
    Thanks!


Log in to reply
 

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