题目描述

给定一棵二叉树，其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法，打印节点数值总和等于某个给定值的所有路径的数量。注意，路径不一定非得从二叉树的根节点或叶节点开始或结束，但是其方向必须向下(只能从父节点指向子节点方向)。

示例:
给定如下二叉树，以及目标和 sum = 22，

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

1 2	3 解释：和为 22 的路径有：[5,4,11,2], [5,8,4,5], [4,11,7]

题解

DFS + 递归

又是一道路径求和的问题, 与剑指OFFER-34题不同的是, 本题需要返回的是满足条件的路径数量而不是具体的路径, 这是降低了难度的, 也就不需要利用回溯法计算了, 不必考虑每次递归后再回退一步.

直观上更偏向于采用先序遍历的方法自顶向下寻找路径. 本题有一个难点在于没有规定必须是从根节点到叶子节点才算是合法路径, 从任意节点开始到任意节点结束只要路径和等于目标值就可以. 所以每往路径里添加一个元素, 就从新添加的地方往前递加, 一旦满足条件就把结果加一.

public class jd0412 {
    int res = 0;

    public int pathSum(TreeNode root, int sum) {
        int dep = depth(root);
        int[] paths = new int[dep];
        pathSum(root, sum, 0, paths);
        return res;

    }

    private void pathSum(TreeNode root, int sum, int level, int[] paths) {
        if (root == null)
            return;

        paths[level] = root.val;
        int temp = 0;
        for (int i = level; i >= 0; i--) {
            temp += paths[i];
            if (temp == sum)
                res++;
        }

        pathSum(root.left, sum, level + 1, paths);
        pathSum(root.right, sum, level + 1, paths);
    }

    private int depth(TreeNode root) {
        if (root == null)
            return 0;
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }
}