NO.112 路径总和 简单
思路一:深搜 和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; 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