使用golang语言编写答案
思路:深度优先搜索,和题目LC37类似,但是不需要使用二维数组保存路径
package main import "fmt" /** * Created by Chris on 2021/8/4. */ type TreeNode struct{ Val int Left *TreeNode Right *TreeNode } func hasPathSum( root *TreeNode , sum int ) bool { return dfs(sum, root) } func dfs(sum int, node *TreeNode) bool{ if node == nil{ return false } sum -= node.Val if node.Left == nil && node.Right == nil && sum == 0{ return true } return dfs(sum, node.Left) || dfs(sum, node.Right) } func main(){ var node1 = &TreeNode{5, nil, nil} var node2 = &TreeNode{4, nil, nil} var node3 = &TreeNode{8, nil, nil} var node4 = &TreeNode{1, nil, nil} var node5 = &TreeNode{11, nil, nil} var node6 = &TreeNode{9, nil, nil} var node7 = &TreeNode{2, nil, nil} var node8 = &TreeNode{7, nil, nil} node1.Left = node2 node2.Right = node3 node2.Left = node4 node2.Right = node5 node3.Right = node6 node5.Left = node7 node5.Right = node8 var sum = 22 var res = hasPathSum(node1, sum) fmt.Println(res) }