Three 4ms c++ solutions given (recursion/ dfs stack based/ bfs queue based)


  • 11
    D

    (1)Recursion, if root is empty, return, if root is a leaf, then return cur+root->val, if root has childrens, then do recursion on each child, with cur updated to cur + root->val +"->"

    class Solution {
        void dfs(vector<string> &res, TreeNode *root, string cur)
        {
            if(!root->left && !root->right) res.push_back(cur  + std::to_string(root->val));
            else
            {
                if(root->left) dfs(res, root->left,  cur  + std::to_string(root->val)+"->");
                if(root->right) dfs(res, root->right, cur  + std::to_string(root->val)+"->");
            }
        }
    public:
        vector<string> binaryTreePaths(TreeNode* root) {
            vector<string> res;
            if(root)  dfs(res, root, "");
            return res;
        }
    };
    

    (2) DFS Version using a stack
    Using a stack (the element is a pair of the current node pointer and the string recording the path from root to the current node). The logic is the same as (1)

    class Solution {
    public:
        vector<string> binaryTreePaths(TreeNode* root) {
            vector<string> res;
            TreeNode *curNode;
            string curPath;
            stack<pair<TreeNode*, string>> liveNodes;
            if(root) liveNodes.push(make_pair(root, ""));
            while(!liveNodes.empty())
            {
                curNode = liveNodes.top().first;
                curPath    = liveNodes.top().second;
                liveNodes.pop();
                if(!curNode->left && !curNode->right)
                {
                    res.push_back(curPath + std::to_string(curNode->val));
                }
                else
                {
                    if(curNode->left)  liveNodes.push(make_pair(curNode->left, curPath + std::to_string(curNode->val)+ "->"));
                    if(curNode->right) liveNodes.push(make_pair(curNode->right, curPath + std::to_string(curNode->val)+ "->"));
                }
            }
            return res;
        }
    };
    

    (3) BFS queue based solution.
    It prints all the paths in an ascending order of the path length

    class Solution {
    public:
        vector<string> binaryTreePaths(TreeNode* root) {
            queue<pair<TreeNode*, string>> liveNodes[2];
            int cur=0, next=1;
            TreeNode* curNode;
            string curPath;
            vector<string> res;
            
            if(root) liveNodes[cur].push(make_pair(root, ""));
            while(!liveNodes[cur].empty())
            {
                curNode = liveNodes[cur].front().first;
                curPath = liveNodes[cur].front().second;
                liveNodes[cur].pop();
                if(!curNode->left && !curNode->right) res.push_back(curPath + std::to_string(curNode->val));
                else{
                    if(curNode->left)  liveNodes[next].push(make_pair(curNode->left,  curPath + std::to_string(curNode->val) + "->"));
                    if(curNode->right) liveNodes[next].push(make_pair(curNode->right, curPath + std::to_string(curNode->val) + "->"));
                }
                if(liveNodes[cur].empty()) swap(cur, next);
            }
            return res;
        }
    };

  • 0
    H

    could you pls explain why not use reference-pass for para "cur" in function dfs, as :

    void dfs(vector<string> &res, TreeNode *root, string & cur)

                                            /|\
    

    ?

    In fact, my idea is almost the same as yours, but I use the reference-pass and I can't pass all the test-case.


  • 0
    D

    If you use pass-by-reference, you have to recover cur everytime you return from a recursive call on a child node since cur will be changed in the recursive call. That is why I used pass-by-value since it guarantees that all the changes made in the recursive calls will not change cur in the current call.


  • 0
    H

    Thanks a lot for your explanation so clearly !!!


Log in to reply
 

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