题目描述
输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。
从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
保证树中结点值均不小于 0。
数据范围
树中结点的数量 [0,1000]。
样例
给出二叉树如下所示，并给出num=22。 5 / \ 4 6 / / \ 12 13 6 / \ / \ 9 1 5 1 输出：[[5,4,12,1],[5,6,6,5]]
方法一：dfs O(n)
思路如下：
递归寻找满足条件的路径，每次递归时都将 sum 减去当前递归到的结点的值，如果此时已经到了叶子结点即左右指针都为空且 sum 刚好为 0 ，则该路径满足要求，直接加入到二维数组 ans 当中。
在递归的过程中要更新 dis 路径，遍历到该结点就加入路径当中，遍历完该结点就从 dis 中删除掉它。
我们拿题目样例举例，来看看是如何实现的：
第一步： 遍历结点 5 ，此时 sum = 22 - 5 = 17 。
第二步： 遍历结点 4 ，此时 sum = 17 - 4 = 13 。
第三步： 遍历结点 12 ，此时 sum = 13 - 12 = 1 。
第四步： 遍历结点 9 ，此时 sum = 1 - 9 = -8 ，并且已经到达叶子结点，但是该路径和不等于 22 ，故不能加入答案 ans 中。
第五步： 回溯再遍历结点 1 ，此时 sum = 1 - 1 = 0 ，并且已经到达叶子结点，路径 [5,4,12,1] 之和等于 22 ，故加入 ans 中。
第六步： 按照上述操作，继续遍历根结点的右子树，同样可以得到另一个路径 [5,6,6,5] 之和也是等于 22 ，故也加入 ans 之中。
第七步： 返回 ans 数组即可。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<vector<int>> ans; vector<int> dis; void dfs(TreeNode* root, int sum) { if (!root) return; sum -= root->val; //减去当前值 dis.push_back(root->val); //如果满足条件，则将dis加入到ans中 if (!root->left && !root->right && !sum) ans.push_back(dis); dfs(root->left, sum); //遍历左子树 dfs(root->right, sum); //遍历右子树 dis.pop_back(); } vector<vector<int>> findPath(TreeNode* root, int sum) { if (!root) return {}; dfs(root, sum); return ans; } };
欢迎大家在评论区交流~
