[LeetCode112. 路径总和] | 刷题打卡

一、题目描述：

给你二叉树的根节点 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,3], targetSum = 5
输出：false

示例 3：

输入：root = [1,2], targetSum = 0
输出：false

二、思路分析：

看到根节点到叶子节点的路径，首先想到dfs。套用dfs的模板，用递归实现需要确定递归的终止条件

1. 当前节点==null，结束递归
2. 当前是叶子节点，叶子节点加上之前节点的sum和target相等。结束递归
3. 向下一层递归，如果左右子节点有一个满足target条件，也结束递归
4. 否则结束递归

以上逻辑可得AC代码如下

三、AC 代码：

class Solution {
    fun hasPathSum(root: TreeNode?, targetSum: Int): Boolean {
        return dfs(root, targetSum, 0)
    }

    fun dfs(root: TreeNode?, targetSum: Int, sum: Int): Boolean {
        if (root == null) {
            return false
        }

        var current = root.`val` + sum
        if (targetSum == current && root.left == null && root.right == null) {
            return true
        }

        if (dfs(root.left, targetSum, current) || dfs(root.right, targetSum, current)) {
            return true
        }
        return false
    }
}

四、总结：

掌握dfs，这确实是easy题

本文正在参与「掘金 2021 春招闯关活动」, 点击查看活动详情