题解 | #二叉树中是否存在节点和为指定值的路径#

使用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)
}