题目描述

https://leetcode-cn.com/problems/binary-tree-paths/

思路

回溯第一题~~~~
果然脑子转不过弯，但是呢呢给讲了下我立马就明白了，在这记录下。
回溯和递归的区别，就是回溯需要修改状态，因此需要恢复现场，而递归不一定。具体说明：
题目中给的二叉树的例子，从1出发找路径，可以去左孩子2，也可以去右孩子3。
往左孩子探的话，路径字符串 1->2。往右孩子探的话，路径字符串1->3.
你探完左孩子，再回到1（回溯），去探右孩子之前，路径字符串必须由1->2再恢复成1（恢复现场），再去探右孩子.
不然探右孩子的时候，路径字符串就变成了1->2->3.
明白了就好写了。
但是这个题，路径字符串可以直接用string，而不是string &，这样就省得回溯回去的时候恢复这个路径字符串了。
然后结合代码，好好体会下就算入门了。
以后要做的八皇后问题也是这样，往下走每一步都有8个选择，每个选择探完回到原点都要恢复现场，再去探下一个选择。

代码

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> paths;
        if (root) findPath(root, paths, "");
        return paths;
    }

    void findPath(TreeNode* root, vector<string>& paths, string s) {
        if (!root->left && !root->right) paths.push_back(s+to_string(root->val));
        if (root->left) findPath(root->left, paths, s + to_string(root->val) + "->");
        if (root->right) findPath(root->right, paths, s + to_string(root->val) + "->");
    }
};

follow up

113. 路径总和 II

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> res;
        vector<int> one;
        if (!root) return res;
        dfs(root, sum, one, res);
        return res;
    }

    void dfs(TreeNode* root, int sum, vector<int> one, vector<vector<int>>& res) {
        one.push_back(root->val);
        if (!root->left && !root->right) {
            if (sum == root->val) {
                res.push_back(one);
            }
        }
        if (root->left) dfs(root->left, sum - root->val, one, res);
        if (root->right) dfs(root->right, sum - root->val, one, res);
    }
};