C++ using backtrack


  • 0
    X
    class Solution {
    public:
        string int2string(int x){
            stringstream ss;
            ss << x;
            string tmp;
            ss >> tmp;
            return tmp;
        }
        void backtrack(TreeNode* root, vector<int>& path, vector<string>& ans){
            if(root == NULL){
                return;
            }else if(root->left == NULL && root->right == NULL){
                string tmp = "";
                for(int i = 0; i < path.size(); ++i){
                    tmp += int2string(path[i]);
                    tmp += "->";
                }
                tmp += int2string(root->val);
                ans.push_back(tmp);
                return;
            }
            if(root->left != NULL){
                path.push_back(root->val);
                backtrack(root->left, path, ans);
                path.pop_back();
            }
            if(root->right != NULL){
                path.push_back(root->val);
                backtrack(root->right, path, ans);
                path.pop_back();
            }
        }
        vector<string> binaryTreePaths(TreeNode* root) {
            vector<int> path;
            vector<string> ans;
            backtrack(root, path, ans);
            return ans;
        }
    };

Log in to reply
 

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