【leetcode】面试题 04.12. 求和路径(dfs)

时间:2020-8-24 作者:admin


题目

【leetcode】面试题 04.12. 求和路径(dfs) 题目链接:面试题 04.12. 求和路径

解题思路

  • 将所求的路径数ans定义为实例变量,并初始化为0。实例变量:独立于方法之外的变量,不过没有static修饰。区别于类变量(独立于方法之外的变量,用static修饰,也叫静态变量)和局部变量(类方法中的变量)。
  • dfs函数从某一结点出发统计以此结点为起始位置的结点数值的总和,当总和等于sum时,ans++。直到当前结点为空时函数返回。
  • pathSum函数返回答案ans,此函数思想也是深度优先搜索主要用于遍历二叉树的结点,同时对遍历到的结点dfs。所以此题有点“双重dfs”的意思。

AC代码:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int ans=0; 
    public void dfs(TreeNode root,int S,int sum){
    if(root==null) return; / /遍历到底的时候就返回 
    if(S+root.val==sum) ans++; / /当前路径总和为sum,ans++
    dfs(root.left,S+root.val,sum); / /往左儿子延展一条路径
    dfs(root.right,S+root.val,sum);  / /往右儿子延展一条路径
    }
    public int pathSum(TreeNode root, int sum) {
    if(root==null) return 0; 
    dfs(root,0,sum); / /从当前结点搜索路径,dfs过程中更新ans
    pathSum(root.left,sum); / /遍历左子树
    pathSum(root.right,sum); // 遍历右子树
    return ans; 
    }
   
}

本题避坑提醒

  • 需要注意的是:结点数值可正可负,所以dfs函数的递归返回条件是当前结点为空(即将每条路径走到底),而不是当前路径数值总和为sum。(若当前路径数值总和为sum,原当前路径走下去也可能会满足“当前路径数值总和为sum”,所以每条路径要走到底)。
  • 先上一份忽略结点数值可正可负导致错误的代码:
/ /114个样例仅通过108个的错误代码:
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int dfs(TreeNode root,int S,int sum){
    if(root==null) return 0;  
    if(S+root.val==sum) return 1;
    return dfs(root.left,root.val+S,sum)+dfs(root.right,S+root.val,sum); 
    }
    public int pathSum(TreeNode root, int sum) {
    if(root==null) return 0;  
    int ans=0;
    ans+=dfs(root,0,sum);
    ans+=pathSum(root.left,sum)+pathSum(root.right,sum);
    return ans; 
    
    }
}
  • 没有通过的一个样例:
    【leetcode】面试题 04.12. 求和路径(dfs)
  • 路径1-> -2 和路径1-> -2 ->1->-1的sum都为-1,所以不能在遍历了路径路径1-> -2 时返回。
声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。