437. 路径总和 III --力扣 --JAVA

2023-12-14 05:17:50

题目

给定一个二叉树的根节点?root?,和一个整数?targetSum?,求该二叉树里节点值之和等于?targetSum?的?路径?的数目。

路径?不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。

解题思路

  1. 从每个节点开始向子节点遍历累加,当前达到目标值是结果加1;
  2. 方法一递归调用方法一;
  3. 方法二以当前节点的值为起始累加,符合结果则加1;

代码展示

class Solution {
    int ans = 0;
    int target;
    public int pathSum(TreeNode root, int targetSum) {
        target = targetSum;
        dfs1(root);
        return ans;
    }
    public void dfs1(TreeNode root){
        if(root == null){
            return;
        }
        dfs2(root,root.val);
        dfs1(root.left);
        dfs1(root.right);
    }
    public void dfs2(TreeNode root, long val){
        if(val == target) {
            ans++;
        } 
        //不用else if避免存在先+后-或先-后+的情况,所以只要还存在子节点就需要遍历
        if (root.left != null) {
            dfs2(root.left, val + root.left.val);
        } 
        if(root.right != null){
            dfs2(root.right, val + root.right.val);
        }
    }
}

文章来源:https://blog.csdn.net/qq_45794129/article/details/134985028
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。