请稍等 ...
×

采纳答案成功!

向帮助你的同学说点啥吧!感谢那些助人为乐的人

Leetcode 112 PathSum DFS解法

bobo老师,我用DFS解了这道题。但是dfs没有返回值,同时维护了一个成员变量findSum(代码如下)。我在想如何改造dfs函数, 使其直接返回true or false,但是失败了。能否请老师看下,如何把dfs改成boolean返回值类型呢?这样直接return dfs就行了


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
     
    private boolean findSum = false;
     
    public boolean hasPathSum(TreeNode root, int targetSum) {
      
        if (root == nullreturn 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回答

看看你能不能理解以下代码?


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
     
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == nullreturn 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;
    }
}

继续加油!:)

0 回复 有任何疑惑可以回复我~
  • 提问者 讲武德的年轻人 #1
    感谢!清晰明了,谢谢老师!
    回复 有任何疑惑可以回复我~ 2022-03-29 05:15:19
  • 老师,下面是我一开始的写法,和你的区别点是:在递归下一层的时候,你是
    if(node.left != null && dfs(node.left, targetSum - node.val)) return true; 
    而我是 if(root.left) return dfs(node.left, targetSum - node.val); // 结果我的提交给leetcode是有报用例失败的,脑子里有那么种感觉,但还是需要老师提示一下哈。。。。。
    ---------------------------------------------------------
    function dfs( root, targetSum ){
        if( root.left == null && root.right == null ){
            return root.val == targetSum
        }
    
       /* 
       if(root.left && dfs( root.left, targetSum - root.val )){
            return true;
        }
    
        if( root.right && dfs( root.right, targetSum - root.val ) ){
            return true;
        } */
    
        // 下面是我刚开始的写法, 如果有子节点,我直接递归子节点了,没再作判断,结果提交leetcode会报错
       if(root.left){
            return dfs( root.left, targetSum - root.val );
        }
    
        if( root.right ){
            return dfs( root.right, targetSum - root.val );
        }
    
        return false;
    }
    回复 有任何疑惑可以回复我~ 2022-03-29 08:28:35
  • 代码的格式是乱掉了,所以我没有看完整的代码。单看 if(root.left) return dfs(node.left, targetSum - node.val); 肯定是错误的。因为这个意思就是,如果左边有节点,且走左边没有相应的路径(即 dfs 返回的是 false),整个函数也就一起返回 false 了。但是对于当前的 root 来说,还可以走右边。有可能右边有正确的路径。继续加油!:)
    回复 有任何疑惑可以回复我~ 2022-03-29 10:03:44
问题已解决,确定采纳
还有疑问,暂不采纳
意见反馈 帮助中心 APP下载
官方微信