题目主要信息

  • 给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum
  • 路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点，如下图所示： alt

方法一：两次dfs过程

具体方法

可以使用两次dfs解决，第一次dfs遍历二叉树每个结点，每个结点都作为一次根结点，第二次dfs遍历以每个结点为根的子树，查找该子树是否有路径和等于目标值的。

Java代码

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型
     */
    static int result = 0;
    public void dfs(TreeNode root,int sum){
        if(root == null){
            return;
        }
        if(sum == root.val){
            result++;
        }
        dfs(root.left,sum-root.val);
        dfs(root.right,sum-root.val);
    }
    public int FindPath (TreeNode root, int sum) {
        // write code here
        //如果为空直接返回
        if(root == null){
            return result;
        }
        dfs(root,sum);
        //遍历左右子树
        FindPath(root.left,sum);
        FindPath(root.right,sum);
        return result;
    }
}

复杂度分析

  • 时间复杂度：O(n2)O(n^2)，其中n为二叉树的结点数，两层dfs嵌套递归
  • 空间复杂度：O(n)O(n)，每层dfs最深递归栈都只有n

方法二：层次遍历+递归

具体方法

在层次遍历的过程中，在每一层的时候，从当前层递归遍历左右子树，找到满足和为路径和为sum的路径个数。并进行统计。

Java代码

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型
     */
    static int result = 0;
    public void cengci(TreeNode root,int sum){
        if(root==null) return;       
        if(sum==root.val) result++;
        //递归遍历左右子树
        cengci(root.left,sum-root.val);
        cengci(root.right,sum-root.val);
    }
    public int FindPath (TreeNode root, int sum) {
        // write code here
        //如果为空直接返回
        if(root==null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(queue.size()!=0){
            TreeNode tmp = queue.poll();
            //遍历当前层
            cengci(tmp, sum);
            if(tmp.left!=null) queue.add(tmp.left);
            if(tmp.right!=null) queue.add(tmp.right);
        }
        return result;
    }
}

复杂度分析

  • 时间复杂度：O(n2)O(n^2)，其中n为二叉树的结点数，两层dfs嵌套递归
  • 空间复杂度：O(n)O(n)，每层dfs最深递归栈都只有n

方法三: 前缀和

具体方法

解法一中应该存在许多重复计算。定义节点的前缀和为：由根结点到当前结点的路径上所有节点的和。我们利用先序遍历二叉树，记录下根节点 root 到当前节点 p 的路径上除当前节点以外所有节点的前缀和，在已保存的路径前缀和中查找是否存在前缀和刚好等于当前节点到根节点的前缀和 currcurr 减去 sum。

  • 对于空路径我们也需要保存预先处理一下，此时因为空路径不经过任何节点，因此它的前缀和为 0。

  • 假设根节点为root，我们当前刚好访问节点 node，则此时从根节点 root 到节点node 的路径（无重复节点）刚好为 root-p1-p2 - ...-pk →p ,此时我们可以已经保存了节点 p1, p2, p3,..., pk的前缀和，并且计算出了节点 node 的前缀和。

  • 假设当前从根节点root 到节点 node 的前缀和为curr，则此时我们在已保存的前缀和查找是否存在前缀和刚好等于 curr−sum。假设从根节点 root 到节点 node 的路径中存在节点p i到根节点root 的前缀和为curr−sum，则节点 pi+1 到 node 的路径上所有节点的和一定为 sum。

  • 利用深度搜索遍历树，当我们退出当前节点时，我们需要及时更新已经保存的前缀和.

alt

Java代码

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型
     */
    public int FindPath(TreeNode root, int sum) {
        //存前缀和
        HashMap<Long, Integer> prefix = new HashMap<>();
        prefix.put(0L, 1);
        //dfs遍历
        return dfs(root, prefix, 0, sum);
    }

    public int dfs(TreeNode root, Map<Long, Integer> prefix, long curr, int targetSum) {
        if (root == null) {
            return 0;
        }

        int ret = 0;
        curr += root.val;//更新当前和
        ret = prefix.getOrDefault(curr - targetSum, 0);
        prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);
        //记录当前和
        ret += dfs(root.left, prefix, curr, targetSum);
        ret += dfs(root.right, prefix, curr, targetSum);
        //放入前缀和中
        prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);

        return ret;
    }
}

复杂度分析

  • 时间复杂度：O(n)O(n)，其中n为二叉树中节点的个数。利用前缀和只需遍历一次二叉树即可。
  • 空间复杂度：O(n)O(n)。存前缀和的空间