Clean C++ Solution - Just a DFS

  • 1

    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 {
        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;
            if (!root->left && !root->right) {
            } else {
                dfs(root->left, paths, stack);
                dfs(root->right, paths, stack);
        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.