目录
- 350-两个数组的交集
- 283-移动零
- 1-两数之和
- 25-K 个一组翻转链表
- 581-最短无序连续子数组
- 合并区间
- 螺旋矩阵
- 数组中相加和为0的三元组
- 数组中出现次数超过一半的数字
- 字符串出现次数的TopK问题
- 206-反转链表
- 160-相交链表
- 19-删除链表的倒数第N个节点
- 21-合并两个有序链表
- 31-下一个排列
- 链表K位翻转
- 链表排序-归并算法
- 判断链表中是否有环
- 设计LRU缓存结构
- 两个链表的第一个公共结点
- 两个链表生成相加链表
- 合并N个有序链表
- 链表内指定区间反转
113.路径总和 II
访问量:1308
一、简介
题目:路径总和II
给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
案例1
输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出:[[5,4,11,2],[5,8,4,5]]
二、实现
思路:递归遍历,1.如果没有子节点,判断当前值是否等于查找的值;2.如果存在子节点,则遍历子节点
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func pathSum(root *TreeNode, targetSum int) [][]int { if root == nil { return nil } var res = make([][]int, 0) doPathSum(root, targetSum, []int{}, &res) return res } func doPathSum(root *TreeNode, targetSum int, curList []int , res *[][]int) { targetSum = targetSum - root.Val curList = append(curList, root.Val) if root.Left == nil && root.Right == nil { if targetSum == 0 { b := make([]int, len(curList)) copy(b, curList) *res = append(*res, b) } return } if root.Left != nil { doPathSum(root.Left, targetSum, curList, res) } if root.Right != nil { doPathSum(root.Right, targetSum, curList, res) } }
本文为原创文章,请尊重辛勤劳动,如需转载,请保留本文地址
若您感觉本站文章不错,读后有收获,不妨赞助一下?
我要赞助