给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

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

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

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

public boolean hasPathSum(TreeNode root, int sum) {

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

        int val = root.val;

        if(root.left==null && root.right==null){
            if(val==sum){
                return true;
            }
            return false;
        }

        //递归调用 左子树值合为sum-val  或   右子树值合为sum-val
        return hasPathSum(root.left, sum-val)||hasPathSum(root.right, sum-val);
    }

核心思路就算递归调用左子树和右子树

修改一下

让你求sum，但是不要求起点包括根节点，也不要求终止点包括叶子节点

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

返回 3。和等于 8 的路径有:

1.  5 -> 3
2.  5 -> 2 -> 1
3.  -3 -> 11

其实就是起始点一直往下走，修改起始点的位置

且每往左子树或者右子树走一次，就要判断下值的情况

public int pathSum(TreeNode root, int sum) {

        if (root == null) {
            return 0;
        }

        //以根节点为基准找路径
        int result = findPath(root, sum);

        //以根节点的左子树、右子树为基准找路径
        result+=pathSum(root.left, sum);
        result+=pathSum(root.right, sum);

        return result;
    }

    public int findPath(TreeNode node, int num) {

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

        int result=0;

        if(node.val==num){
            result+=1;
        }
        
        //因为存在负数，所以就算找到一个result也还需要继续往下走 
        result+=findPath(node.left, num-node.val);
        result+=findPath(node.right, num-node.val);

        return result;
    }

转载请注明：汪明鑫的个人博客 » 每周一练（15）