题解 | #二叉树中和为某一值的路径(一)#

递归分解问题

题目要求根节点到叶子节点有没有等于sum值的路径，返回的是布尔值，因此可判断当前节点是否为叶子节点，如果是叶子节点就判断叶子节点的值是否为sum，如果不是则分解为子问题，即将sum减去当前值然后到左右子树中查找。

题目返回的布尔值是自底向上从叶子节点依次返回的，即上一层的函数的返回值依赖于下一层的布尔值，并且每一层都加了||判断，如果左子树或右子树任何一个满足条件都会返回true，如果叶子节点的值不为sum，则他左右子树返回的结果必然为false。

参考

参考题解

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    
    public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        if (root == null) {
            return false;
        }
		
	    // 当前是叶子节点，且叶子节点的值等于总和
        if (root.left == null && root.right == null && sum - root.val == 0) {
            return true;
        }
	    // 递归解决子问题，子问题为当前sum减去当前节点的值剩下的sum，给左右子树寻找是否有等于子问题的路径
        return hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum-root.val);
    }
}