长大后想做什么？做回小孩！

0%

LeetCode——路径总和

发表于 分类于 Valine：
本文字数： 173

NO.112 路径总和 简单

JE4Xh8.png

思路一：深搜 和NO.39组合总和、NO.40组合总和II有点像，不过本题已经是树形结构找路径了。采用相同的思路，深搜sum每次减掉已经走过的节点值，sum表示还需要多少才能符合要求。sum==0表示路径和符合要求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean hasPathSum(TreeNode root, int sum) {
    return dfs(root, sum);
}

private boolean dfs(TreeNode root, int sum) {
    if (root == null) return false;
    sum -= root.val;
    //到达叶子节点，返回路径和是否等于0
    if (root.left == null && root.right == null) {
        return sum == 0;
    }
    //左右子树是否存在符合要求的路径
    boolean left = dfs(root.left, sum);
    boolean right = dfs(root.right, sum);
    return left || right;
}

时间复杂度：O(n) 深度优先遍历一次，前序遍历

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github