目录
- 350-两个数组的交集
- 283-移动零
- 1-两数之和
- 25-K 个一组翻转链表
- 581-最短无序连续子数组
- 合并区间
- 螺旋矩阵
- 数组中相加和为0的三元组
- 数组中出现次数超过一半的数字
- 字符串出现次数的TopK问题
- 206-反转链表
- 160-相交链表
- 19-删除链表的倒数第N个节点
- 21-合并两个有序链表
- 31-下一个排列
- 链表K位翻转
- 链表排序-归并算法
- 判断链表中是否有环
- 设计LRU缓存结构
- 两个链表的第一个公共结点
- 两个链表生成相加链表
- 合并N个有序链表
- 链表内指定区间反转
二叉树路径总和
访问量:1696
一、简介
给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树,以及目标和 sum = 22
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2
二、代码实现
1、递归版本
type Queue struct { data []*TreeNode } func (q *Queue) Push(n *TreeNode) { if q.data == nil { q.data = make([]*TreeNode, 0) } q.data = append(q.data, n) } func (q *Queue) Pop() *TreeNode { if len(q.data) == 0 { return nil } node := q.data[0] q.data = q.data[1:] return node } func (q *Queue) Len() int { return len(q.data) } /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func hasPathSum(root *TreeNode, sum int) bool { if root == nil { return false } if root.Left == nil && root.Right == nil { return root.Val == sum } if root.Left != nil { isOk := hasPathSum(root.Left, sum - root.Val) if isOk { return true } } if root.Right != nil { isOk := hasPathSum(root.Right, sum - root.Val) if isOk { return true } } return false }
本文为原创文章,请尊重辛勤劳动,如需转载,请保留本文地址
若您感觉本站文章不错,读后有收获,不妨赞助一下?
我要赞助