Open youngyangyang04 opened 5 months ago
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) return false; // 回溯
sum -= root.val;
if (root.left == null && root.right == null && sum == 0) {
return true; // 满足
}
return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
}
}
class Solution {
List<List<Integer>> paths = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
traverse(root, sum);
return paths;
}
private void traverse(TreeNode node, int sum) {
if(node == null) return; // 回溯
path.add(node.val);
sum -= node.val;
if (node.left == null && node.right == null && sum == 0) {
paths.add(new ArrayList<>(path)); // 满足
} else {
traverse(node.left, sum);
traverse(node.right, sum);
}
path.remove(path.size() - 1); // 剪支
}
}
112做法
class Solution {
public:
bool flag = false;
void traversal(TreeNode * node,vector<int>& path,int target){
path.push_back(node->val);
//碰到叶子节点
if(node->left == nullptr and node->right == nullptr){
int sum = 0;
for(auto temp : path){
sum += temp;
}
if(sum == target) flag = true;
}
if(node->left){
traversal(node->left,path,target);
path.pop_back();//回溯
}
if(node->right){
traversal(node->right,path,target);
path.pop_back();
}
}
bool hasPathSum(TreeNode* root, int targetSum) {
if(root == nullptr) return false;
vector<int> path;
traversal(root,path,targetSum);
return flag;
}
};
113做法
class Solution {
public:
void traversal(TreeNode * node,vector<int>& path,vector<vector<int>>& result,int target){
s path.push_back(node->val);
if(node->left == nullptr and node->right == nullptr){
int sum = 0;
for(auto temp : path){
sum += temp;
}
if(sum == target) result.push_back(path);
}
if(node->left){
traversal(node->left,path,result,target);
path.pop_back();//回溯到当前
}
if(node->right){
traversal(node->right,path,result,target);
path.pop_back();
}
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
if(root == nullptr) return vector<vector<int>>();
vector<vector<int>> result;
vector<int> path;
traversal(root,path,result,targetSum);
return result;
}
};
"是不是发现精简之后的代码,已经完全看不出分析的过程了?"
bool hasPathSum(TreeNode* root, int sum) {
if (!root) return false;
if (!root->left && !root->right && sum == root->val) {
return true;
}
return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}
这个代码其实可以很声明式理解:
定义一个函数 hasPathSum(root, sum)
: 是否可以从 root 出发找到一条 path,这个 path 其和为 sum。
根据这个函数定义,很容易找到两个 base cases:
接着找到一个归纳的条件:当左子树或右子树有一条 path 的和为 sum - root.val时,存在一个 path 从当前节点 root 出发其和为 sum。
这个声明式定义可以说是自带数学证明的,也可以一步到位,完全没考虑怎么套 preorder 的模板🤣
https://www.programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html