二叉树的所有路径

方法：递归（回溯）

class Solution {
public:
    void traversal(TreeNode* cur, vector &path, vector &res) {
        path.push_back(cur->val);              //中
        if (cur->left == nullptr && cur->right == nullptr) {
            string t;
            for (int i = 0; i < path.size() - 1; i++) {
                t += to_string(path[i]);
                t += "->";
            }
            t += to_string(path[path.size() - 1]);
            res.push_back(t);
            return;
        }
        if (cur->left) {                  //左
            traversal(cur->left, path, res);
            path.pop_back();        //回溯
        }
        if (cur->right) {                  //右
            traversal(cur->right, path, res);
            path.pop_back();           //回溯
        }
    }

    vector binaryTreePaths(TreeNode* root) {
        vector res;
        vector path;
        if (root == nullptr) {
            return res;
        }
        traversal(root, path, res);
        return res;
    }
};

 思路：因为求的是所有路径，很明显得用先序遍历，然后写个没有返回值的先序遍历的函数，（注意：培养个习惯，写的函数主要是注重函数的形参，不必太注意返回值，能把返回值放到形参里就放，但是得注意加上  &  ），然后就是注意回溯的时候，要记住回溯和递归是绑在一起的，每次递归的时候都要回溯，所以递归左子树和右子树的时候都要回溯，还有就是注意要最开始就把中间结点push进去，不然函数终止的if语句会出现问题，因为当时并没有把所有结点都放进path。

知识点：函数  to_string()

简洁版

class Solution {
private:

    void traversal(TreeNode* cur, string path, vector& result) {
        path += to_string(cur->val); // 中
        if (cur->left == NULL && cur->right == NULL) {
            result.push_back(path);
            return;
        }
        if (cur->left) traversal(cur->left, path + "->", result); // 左
        if (cur->right) traversal(cur->right, path + "->", result); // 右
    }

public:
    vector binaryTreePaths(TreeNode* root) {
        vector result;
        string path;
        if (root == NULL) return result;
        traversal(root, path, result);
        return result;

    }
};