二叉树--是否存在路径之和等于给定值

今天学习的算法是给定一课二叉树，判断是否存在一条路径其值之和等于给定的值。

题目介绍

从根节点到每一条叶子节点表示一条路径，只要有一条路径的值之和等于给定值就返回true，否则返回false。我们先看下题目给定的树吧：

实现思路

还是使用递归的思想来解题吧，先看下实现思路图：

二叉树-是否存在路径之和等于给定值-解题（优化）.png

按之前说过的递归代码最重要的是两点： 1、找到递归公式 2、找到终止条件

从图中我们可以看出，我们使用的是前序遍历来实现的。先遍历中间节点，计算从根节点到当前中间节点的路径之和（上图中的SUM），然后分别递归遍历左子节点和右子节点。因此得出以下两点：

1、递归公式：F(node,sum,presum) = (sum==presum+node.val) || F(node.left,sum,presum) || F(node.right,sum,presum) 。

2、终止条件：node == null 或者 node为叶子节点且sum等于给定值。

实现代码

public class SolutionHasPathSum {

    public boolean hasPathSum(TreeNode root, int sum) {
        return hasPathSum(root, sum, 0);
    }

    private boolean hasPathSum(TreeNode node, int sum, int preSum) {

        if(node == null){
            return false;
        }

        preSum += node.val;
        if (null == node.left && null == node.right) {
            return sum == preSum;
        }

        return hasPathSum(node.left, sum, preSum) || hasPathSum(node.right, sum, preSum);
    }

}

算法相关实现源码地址：https://github.com/xiekq/rubs-algorithms