二叉树中和为某一值的路径

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

来自牛客 剑指offer

题目描述

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

vector<vector<int> > vv;
vector<int> v;
void DFS(TreeNode* root, int expectNumber) {
    v.push_back(root->val);
    expectNumber -= root->val;
    if (!root->left && !root->right && !expectNumber) {
        vv.push_back(v);
    } 
    if (root->left) {
        DFS(root->left, expectNumber);
        v.erase(v.end() - 1);
    }
    if (root->right) {
        DFS(root->right, expectNumber);
        v.erase(v.end() - 1);
    }
}
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
    if (!root) return vv;
    DFS(root, expectNumber);
    sort(vv.begin(), vv.end(), [](auto a, auto b) { return a.size() > b.size(); });
    return vv;
}