长大后想做什么?做回小孩!

0%

LeetCode——路径总和

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