112.路径总和

递归

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

}

栈方法

func hasPathSum(root *TreeNode, targetSum int) bool {
     if root == nil {
          return false
     }
     
     stack := []struct {
          node *TreeNode
          sum  int
     }{{root, targetSum}}
     
     for len(stack) > 0 {
          current := stack[len(stack)-1]
          stack = stack[:len(stack)-1]
     
          node, sum := current.node, current.sum
          sum -= node.Val
     
          if node.Left == nil && node.Right == nil && sum == 0 {
              return true
          }
     
          if node.Right != nil {
              stack = append(stack, struct {
                  node *TreeNode
                  sum  int
              }{node.Right, sum})
          }
     
          if node.Left != nil {
              stack = append(stack, struct {
                  node *TreeNode
                  sum  int
              }{node.Left, sum})
          }
     }
     
     return false
}