OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Go›Go教程

路径和问题大击破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

}