Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

    Note: A leaf is a node with no children.

    Example:

    Given the below binary tree and sum = 22,

    1.             5
    2.      / \
    3.     4   8
    4.    /   / \
    5.   11  13  4
    6.  /  \      \
    7. 7    2      1

    return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

    题意

    判断给定树中是否存在这样一条从根到叶的路径，使得路径上的数字之和等于目标值。

    思路

    回溯法。

    代码实现

    1. /**
    2.  * Definition for a binary tree node.
    3.  * public class TreeNode {
    4.  *     int val;
    5.  *     TreeNode left;
    6.  *     TreeNode right;
    7.  *     TreeNode(int x) { val = x; }
    8.  * }
    9.  */
    10. class Solution {
    11.     public boolean hasPathSum(TreeNode root, int sum) {
    12.         return hasPathSum(root, 0, sum);
    13.     }
    15.     private boolean hasPathSum(TreeNode x, int preSum, int sum) {
    16.         if (x == null) {
    17.             return false;
    18.         }
    19.         // 路径数字和等于目标值且当前结点为叶结点，说明找到了
    20.         if (preSum + x.val == sum && x.left == null & x.right == null) {
    21.             return true;
    22.         }
    25.         if (hasPathSum(x.left, preSum + x.val, sum)) {
    26.             return true;
    27.         }
    28.         if (hasPathSum(x.right, preSum + x.val, sum)) {
    29.             return true;
    30.         }
    32.         return false;
    33.     }
    34. }