• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    迪恩网络公众号

路径和问题大击破Go版本

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
示例:

输入:
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

输出:返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

func hasPathSum(root *TreeNode, sum int) bool {
    if root == nil{
        return false
    }
    if root.Left==nil && root.Right == nil{
        return root.Val == sum
    }
    return hasPathSum(root.Left,sum-root.Val) || hasPathSum(root.Right,sum-root.Val)
}

Leetcode 113:路径总和 II

给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

func FindPath( root *TreeNode ,  expectNumber int ) [][]int {
    // write code here
    if root == nil{
        return nil
    }
    res := make([][]int,0)
    path := []int{}
    getWay(root,path,expectNumber,&res)
    return res
}
func getWay(root *TreeNode, path []int,sum int,res *[][]int){
    if root == nil {
        return
    }
    path = append(path, root.Val)
    if sum == root.Val && root.Left==nil && root.Right==nil{
//         dst := make([]int,len(path)+1)
        *res = append(*res, path)
    }
    getWay(root.Left,path,sum-root.Val,res)
    getWay(root.Right,path,sum-root.Val,res)
    path = path[:len(path)-1]
}

  

Leetcode 437:路径总和 III

给定一个二叉树,它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。
二叉树不超过1000个节点,且节点数值范围是 [-1000000,1000000] 的整数。

func pathSum(root *TreeNode, sum int) int {
    if root == nil{
        return 0
    }
    return hasPath(root,sum,0)+pathSum(root.Left,sum)+pathSum(root.Right,sum)
}
func hasPath(root *TreeNode,sum,count int) int{
    if root == nil{
        return count
    }
    sum-=root.Val
    if 0 == sum {
        count++
    }
    count = hasPath(root.Left,sum,count)
    count = hasPath(root.Right,sum,count)
    return count

}

  

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Inheritance and subclassing in Go - or its near likeness发布时间:2022-07-10
下一篇:
Go语言的几个Web开发框架 - 蝈蝈俊发布时间:2022-07-10
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap