路径总和III

type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}

package main
// 路径总和III
import (
  "awesomeProject/leetcode01"
  "fmt"
  "strconv"
)
var res int = 0
func main() {
  valSlice := []string{"5", "4", "8", "11", "", "13", "4", "7", "2", "", "", "5", "1"}
  root := createTree(valSlice)
  pathSum(root, 22)
  fmt.Println("res ", res)
}
func pathSum(root *leetcode01.TreeNode, targetSum int) {
  preList := make([]int, 0)
  preList = append(preList, 0)
  preOrder(root, targetSum, &preList)
  //preOrderTest(root, targetSum, preList)
}
// 由于传入的是地址指针，因此共用一个slice，需要回溯结果
func preOrder(root *leetcode01.TreeNode, targetSum int, preListPtr *[]int) {
  if root == nil {
    return
  }
  for i := 0; i < len(*preListPtr); i++ {
    (*preListPtr)[i] = (*preListPtr)[i] + root.Val
    if (*preListPtr)[i] == targetSum {
      res++
    }
  }
  *preListPtr = append(*preListPtr, 0)
  fmt.Printf("%p\n", preListPtr)
  preOrder(root.Left, targetSum, preListPtr)
  preOrder(root.Right, targetSum, preListPtr)
  // 回溯
  *preListPtr = (*preListPtr)[:len(*preListPtr)-1]
  for i := 0; i < len(*preListPtr); i++ {
    (*preListPtr)[i] = (*preListPtr)[i] - root.Val
  }
}
// 切片通过append以后返回的是一个新的地址，因此不需要回溯
func preOrderTest(root *leetcode01.TreeNode, targetSum int, preList []int) {
  if root == nil {
    return
  }
  // 这里返回的是一个新的list
  preList = append(preList, 0)
  //fmt.Printf("%p\n", &preList)
  for i := 0; i < len(preList)-1; i++ {
    preList[i] = preList[i] + root.Val
    if preList[i] == targetSum {
      res++
    }
  }
  preOrderTest(root.Left, targetSum, preList)
  preOrderTest(root.Right, targetSum, preList)
}
// 构造树
func createTree(valSlice []string) *leetcode01.TreeNode {
  val, _ := strconv.Atoi(valSlice[0])
  root := &leetcode01.TreeNode{
    Val:   val,
    Left:  nil,
    Right: nil,
  }
  var queue = make([]*leetcode01.TreeNode, 0)
  queue = append(queue, root)
  var i = 1
  for len(queue) != 0 && i < len(valSlice) {
    p := queue[0]
    queue = queue[1:]
    // 构造左子树
    if valSlice[i] != "" {
      val, _ = strconv.Atoi(valSlice[i])
      left := &leetcode01.TreeNode{
        Val:   val,
        Left:  nil,
        Right: nil,
      }
      p.Left = left
      queue = append(queue, left)
    }
    i++
    // 构造右子树
    if i < len(valSlice) && valSlice[i] != "" {
      val, _ = strconv.Atoi(valSlice[i])
      right := &leetcode01.TreeNode{
        Val:   val,
        Left:  nil,
        Right: nil,
      }
      p.Right = right
      queue = append(queue, right)
    }
    i++
  }
  return root
}