LeetCode-112-路径总和

路径总和

题目描述:给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ,判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。

叶子节点 是指没有子节点的节点。

示例说明请见LeetCode官网。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/path-sum/
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解法一:递归

首先,如果root为null,直接返回false。

否则,调用递归方法hasPathSum(TreeNode root, int targetSum, int curSum),root为当前节点,targetSum为目标和,curSum当前路径上的累加和,递归过程如下:

  • 如果root为null,直接返回;
  • 否则,curSum累加当前节点的值;
  • 然后判断如果root的左子树或者右子树有一边为null,则调用递归方法,参数为不为null的子树和curSum,然后返回;
  • 如果root的左子树和右子树都不为null,则左右子树都要调用递归方法。

过程中当到达子节点时需要判断当前路径的和curSum和targetSum是否相等,如果相等,则将result更新为true,最后返回result。

说明:该题的解法过程和 LeetCode-111-二叉树的最小深度 完全一样。

public class LeetCode_112 {
    public static boolean result = false;

    public static boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        hasPathSum(root, targetSum, 0);
        return result;
    }

    public static void hasPathSum(TreeNode root, int targetSum, int curSum) {
        if (root == null) {
            return;
        }
        curSum += root.val;
        if (root.left == null && root.right == null) {
            if (curSum == targetSum) {
                result = true;
            }
            return;
        }
        if (root.left == null && root.right != null) {
            hasPathSum(root.right, targetSum, curSum);
            return;
        }
        if (root.left != null && root.right == null) {
            hasPathSum(root.left, targetSum, curSum);
            return;
        }
        hasPathSum(root.left, targetSum, curSum);
        hasPathSum(root.right, targetSum, curSum);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        System.out.println(hasPathSum(root, 5));
        System.out.println(hasPathSum(root, 4));
    }
}

【每日寄语】 收集每一个快乐的瞬间,用它来回击每一个糟糕的日子。

上一篇:#2021牛客暑假多校3_E.Math_数论打表


下一篇:112_Git的历史记录查看