Leetcode 112 PathSum DFS解法

Question

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);
            
        }
    }
   
}

Answer 1

liuyubobobo 2022-03-29 04:02:49

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

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;
    }
}

继续加油！：）

• 提问者 讲武德的年轻人 #1

  感谢！清晰明了，谢谢老师！

• 甲骨文_0001 #2

  老师，下面是我一开始的写法，和你的区别点是：在递归下一层的时候，你是
  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;
  }

• liuyubobobo 回复 甲骨文_0001 #3

  代码的格式是乱掉了，所以我没有看完整的代码。单看 if(root.left) return dfs(node.left, targetSum - node.val); 肯定是错误的。因为这个意思就是，如果左边有节点，且走左边没有相应的路径（即 dfs 返回的是 false），整个函数也就一起返回 false 了。但是对于当前的 root 来说，还可以走右边。有可能右边有正确的路径。继续加油！：）

点开查看后面1条评论