Leetcode 112 PathSum DFS解法
来源：7-4 注意递归的终止条件 Path Sum
讲武德的年轻人
2022-03-29
bobo老师，我用DFS解了这道题。但是dfs没有返回值，同时维护了一个成员变量findSum(代码如下)。我在想如何改造dfs函数， 使其直接返回true or false，但是失败了。能否请老师看下，如何把dfs改成boolean返回值类型呢？这样直接return dfs就行了
class Solution {
private boolean findSum = false;
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
dfs(root, root.val, targetSum);
return findSum;
}
private void dfs(TreeNode node, int sum, int targetSum) {
if (node.left == null && node.right == null) {
if (sum == targetSum) {
findSum = true;
return;
}
} else {
if (node.left != null)
dfs(node.left, sum + node.left.val, targetSum);
if (node.right != null)
dfs(node.right, sum + node.right.val, targetSum);
}
}
}写回答
1回答
-
看看你能不能理解以下代码？
class Solution { public boolean hasPathSum(TreeNode root, int targetSum) { if(root == null) return false; return dfs(root, targetSum); } // 寻找从 node 出发，有没有一条从 node 到叶子的路径，其和为 targetSum private boolean dfs(TreeNode node, int targetSum) { if (node.left == null && node.right == null){ return targetSum == node.val; } if(node.left != null && dfs(node.left, targetSum - node.val)) return true; if(node.right != null && dfs(node.right, targetSum - node.val)) return true; return false; } }继续加油！：）
042022-03-29
相似问题