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

/*
 *此题与之前的二叉树层序遍历和二叉树最大深度有异曲同工之妙。因此我们可以使用队列按常规方式求解。也可以使用递归方式求解。下面展示的是递归方式求解的代码。
 */
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;
        }
        return getPathSum(root,sum,0);
    }
    public boolean getPathSum(TreeNode node ,int targerSum,int curSum){
        if(node.left == null && node.right == null){
            return curSum+node.val == targerSum;
        }
        if(node.left == null){
            return getPathSum(node.right,targerSum,curSum+node.val);
        }
        if(node.right == null){
            return getPathSum(node.left,targerSum,curSum+node.val);
        }
        return getPathSum(node.right,targerSum,curSum+node.val)||getPathSum(node.left,targerSum,curSum+node.val);
    } 
}