【LeetCode】路径总和 Java 题解

关注

发布于: 3 小时前

题目描述

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

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

示例 1：输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22输出：true

示例 2：
输入：root = [1,2], targetSum = 0输出：false
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/path-sum著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的每日一题是求路径和的问题，题干明确指出是从根节点到叶子节点的和，因此，需要遍历整颗树，采用递归的解法。
如何判断叶子节点？叶子节点的左子树，右子树都是 null。利用这个条件，可以写出如下代码。

通过代码

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode() {} *     TreeNode(int val) { this.val = val; } *     TreeNode(int val, TreeNode left, TreeNode right) { *         this.val = val; *         this.left = left; *         this.right = right; *     } * } */class Solution {    public boolean hasPathSum(TreeNode root, int targetSum) {        if (root == null) {            return false;        }        if (root.left == null && root.right == null) {            return root.val == targetSum;        }
        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }}

复制代码

总结

上述代码的时间复杂度是 O(n), 空间复杂度是 O(n)
坚持算法每日一题，加油！

发布于: 3 小时前阅读数: 2

原文链接:【http://xie.infoq.cn/article/57f7e092434c036a5aacfb397】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】路径总和 Java 题解

题目描述

思路分析

通过代码

总结

HQ数字卡

评论