求和路径

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

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

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
返回:

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

节点总数 <= 10000
通过次数9,725提交次数20,108

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/paths-with-sum-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

不求树的深度的修改

class Solution {
    public int pathSum(TreeNode root, int sum) {
        if (root == null && sum == 0) return 0;
        if (root == null) return 0;
        deep(root, new ArrayList<>(), sum);
        return res;
    }

    int res = 0;

    public void deep(TreeNode root, List<Integer> list, int sum) {
        if (root == null) return;
        list.add(root.val);
        int curSum = 0;
        for (int i = list.size() - 1; i >= 0; i--) {
            //必须要自叶子节点方向向根节点方向求和，不然会重复计数
            curSum += list.get(i);
            if (curSum == sum) res++;
        }
        deep(root.left, list, sum);
        deep(root.right, list, sum);
        list.remove(list.size() - 1);
    }

}

直接暴力递归

分别计算当前的节点和左子树与右子树的满足路径和等于sum的路径数量，并对三个计算的结果求和

class Solution {
    int res=0;
    public int pathSum(TreeNode root, int sum) {
        if(root==null) return 0;
        return dfs(root,sum)+pathSum(root.left,sum)+pathSum(root.right,sum);        //检查根节点的和，检查左右子树的和
    }
    private int dfs(TreeNode root,int sum){
        if(root==null) return 0;
        sum-=root.val;
        return (sum==0?1:0)+dfs(root.left,sum)+dfs(root.right,sum);                 //如果当前节点的和等于sum，继续计算到叶子节点，因为其有负数
    }
}

不使用容器，首先求树的深度

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int pathSum(TreeNode root, int sum) {
        int dep = depth(root);
        int[] paths = new int[dep];
        pathSum(root, sum, 0, paths);
        return res;
    }

    int res = 0;

    public void pathSum(TreeNode root, int sum, int level, int[] paths) {
        if (root == null) {
            return;
        }
        paths[level] = root.val;
        int t = 0;
        for (int i = level; i >= 0; i--) {
            t += paths[i];
            if (t == sum) {
                res += 1;
            }
        }
        pathSum(root.left, sum, level + 1, paths);
        pathSum(root.right, sum, level + 1, paths);
    }

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

参考文献

作者：dadou来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

作者：geguanting来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信