可以从两个角度来想:
1. 在dfs遍历树的过程中,增加一些操作,使得可以寻找二叉树中和为某一值的路径。由于需要记录路径,我们在访问到某节点时,将其push进path
向量,在访问完其时,将其pop出path
向量。path
向量中保存的一直是从根节点到当前正在访问的节点的路径。当遍历到叶子节点时,如果此时sum==target
,我们就将path
存入res
当中去。
2. 分治的思想,将一个大问题分解为数个小问题。我们要求一棵树中和为某一值的路径,可以分解为以其左右儿子为根的、和为target-root->val
的路径。那么,每一层的操作就是,判断当前访问的节点是否为叶子节点,如果是的话,判断sum
是否等于target
;如果不是的话,继续分治为两个子问题。终止条件就是,如果当前访问的是空节点,那么无法继续分治,直接返回。
算法1
递归 $O(n)$
C++ 代码
/**
* 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> path;
vector<vector<int>> findPath(TreeNode* root, int sum) {
dfs(root,sum);
return ans;
}
void dfs(TreeNode *root, int sum){
if (!root) return;
path.push_back(root->val);
sum -= root->val;
if (!root->left && !root->right && !sum ) ans.push_back(path);
dfs(root->left,sum);
dfs(root->right,sum);
path.pop_back();
}
};
化简版
牛客网: 二叉树中和为某一值的路径
给定一个二叉树root和一个值 sum ,判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。
C++ 代码
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
//空节点找不到路径
if(root == NULL)
return false;
//叶子节点,且路径和为sum
if(root->left == NULL && root->right == NULL && sum - root->val == 0)
return true;
//递归进入子节点
return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}
};