[LeetCode] 437. 路径总和 III ☆☆☆(递归)
2023-09-14 09:07:34 时间
路径总和 III
描述
给定一个二叉树,它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。
二叉树不超过1000个节点,且节点数值范围是 [-1000000,1000000] 的整数。
示例:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
返回 3。和等于 8 的路径有:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
解析
1. 遍历每个节点。 关键点:递归
2. 计算以当前节点为路径终点的所有路径和。 关键点:用一个数组保存从根节点到当前节点路径
代码
public int pathSum(TreeNode root, int sum) { if (null == root) { return 0; } return pathSumHelp(root, new int[1000], sum, 0); } /** * * @param root * @param array 保存路径的数组 * @param sum * @param curIndex 当前的数组index * @return */ public int pathSumHelp(TreeNode root, int[] array, int sum, int curIndex) { if (null == root) { return 0; } int curNum = root.val == sum ? 1 : 0; int curSum = root.val; for (int i = curIndex - 1; i >= 0; i--) { curSum += array[i]; if (curSum == sum) { curNum++; } } array[curIndex] = root.val; int leftNum = pathSumHelp(root.left, array, sum, curIndex + 1); int rightNum = pathSumHelp(root.right, array, sum, curIndex + 1); return curNum + leftNum + rightNum; }
复杂度
遍历n个节点,为每个节点计算以当前节点为路径终点的所有路径和,平均路径长度是logn,所以平均时间复杂度是O(nlogn)
相关文章
- Leetcode 之Binary Tree Postorder Traversal(46)
- Java实现 LeetCode 815 公交路线(创建关系+BFS)
- Java实现 LeetCode 779 第K个语法符号(递归)
- Java实现 LeetCode 779 第K个语法符号(递归)
- Java实现 LeetCode 736 Lisp 语法解析(递归)
- Java实现 LeetCode 731 我的日程安排表 II(二叉树)
- Java实现 LeetCode 690 员工的重要性(简易递归)
- Java实现 LeetCode 687 最长同值路径(递归)
- Java实现 LeetCode 679 24 点游戏(递归)
- Java实现 LeetCode 654 最大二叉树(递归)
- Java实现 LeetCode 653 两数之和 IV - 输入 BST(递归,找差值)
- Java实现 LeetCode 650 只有两个键的键盘(递归 || 数学)
- Java实现 LeetCode 523 连续的子数组和(ง •_•)ง
- Java实现 LeetCode 189 旋转数组
- Java实现 LeetCode 12 整数转罗马数字
- LeetCode-1615. 最大网络秩【图】
- LeetCode-357. 统计各位数字都不同的数字个数【排列组合,递归,动态规划】
- Leetcode 1037. 有效的回旋镖
- LeetCode Pow(x, n)-简单粗暴法解决
- [LeetCode] 746. 使用最小花费爬楼梯 ☆(动态规划)
- [LeetCode] 95. 不同的二叉搜索树 II ☆☆☆(递归,n个数组成的所有二叉搜索树)
- leetcode 458. Poor Pigs
- leetcode 122. Best Time to Buy and Sell Stock II
- 【Leetcode刷题Python】199. 二叉树的右视图
- 【Leetcode刷题Python】剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
- 【Leetcode刷题Python】300. 最长递增子序列
- 【LeetCode】238. 除自身以外数组的乘积