11-lines 4ms C++ Backtracking Code


  • 0

    The basic idea is to start from root and add it to the current path, then we recursively visit its left and right subtrees if they exist; otherwise, we have reached a leaf node, so just add the current path to the result paths.

    The code is as follows.

    class Solution {
    public:
        vector<string> binaryTreePaths(TreeNode* root) {
            vector<string> paths;
            string path;
            treePaths(root, path, paths);
            return paths;
        }
    private:
        void treePaths(TreeNode* node, string path, vector<string>& paths) {
            if (!node) return;
            path += path.empty() ? to_string(node -> val) : "->" + to_string(node -> val);
            if (!(node -> left) && !(node -> right)) {
                paths.push_back(path);
                return;
            }
            if (node -> left) treePaths(node -> left, path, paths);
            if (node -> right) treePaths(node -> right, path, paths);
        }
    };

Log in to reply
 

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