Clean C++ Solution - Just a DFS


  • 1
    S

    The idea is simple: perform a depth-first search and take a "snapshot" of the stack whenever a leaf node is reached.

    Probably not the shortest solution, but I thought this was cleaner as it doesn't mix how data is stored with how the question wants the data displayed.

    class Solution {
    public:
        vector<string> binaryTreePaths(TreeNode* root) {
            vector<string> listPaths;
            vector<int> dfsStack;
            dfs(root, listPaths, dfsStack);
            return listPaths;
        }
        
        void dfs(TreeNode* root, vector<string>& paths, vector<int>& stack) {
            if (!root) return;
            stack.push_back(root->val);
            if (!root->left && !root->right) {
                paths.push_back(getPathFormat(stack));
            } else {
                dfs(root->left, paths, stack);
                dfs(root->right, paths, stack);
            }
            stack.pop_back();
        }
    
        string getPathFormat(const vector<int>& stack) {
            string out = "";
            for (auto it = stack.begin(); it != stack.end(); ++it) {
                out += std::to_string(*it);
                if (it + 1 != stack.end()) out += "->";
            }
            return out;
        }
    };
    

Log in to reply
 

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