二叉树专题（7）

112. 路径总和 Path Sum

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22

输出：true

解释：等于目标和的根节点到叶节点路径如上图所示。

示例 2：

输入：root = [1,2,3], targetSum = 5

输出：false

解释：树中存在两条根节点到叶子节点的路径：

(1 --> 2): 和为 3

(1 --> 3): 和为 4

不存在 sum = 5 的根节点到叶子节点的路径。

示例 3：

输入：root = [], targetSum = 0

输出：false

解释：由于树是空的，所以不存在根节点到叶子节点的路径。

提示：

树中节点的数目在范围 [0, 5000] 内

-1000 <= Node.val <= 1000

-1000 <= targetSum <= 1000

代码：

package main
import (
  "fmt"
)
const null = -1 << 31
type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}
func hasPathSum(root *TreeNode, targetSum int) bool {
  sum := func(arr []int) int {
    res := 0
    for i := 0; i < len(arr); i++ {
      res += arr[i]
    }
    return res
  }
  for _, path := range binaryTreePaths(root) {
    if sum(path) == targetSum {
      return true
    }
  }
  return false
}
func binaryTreePaths(root *TreeNode) [][]int {
  res := [][]int{}
  if root == nil {
    return res
  }
  if root.Left == nil && root.Right == nil {
    return [][]int{{root.Val}}
  }
  leftPaths := binaryTreePaths(root.Left)
  rightPaths := binaryTreePaths(root.Right)
  paths := make([][]int, 0)
  for _, path := range leftPaths {
    paths = append(paths, append([]int{root.Val}, path...))
  }
  for _, path := range rightPaths {
    paths = append(paths, append([]int{root.Val}, path...))
  }
  return paths
}
func buildTree(nums []int) *TreeNode {
  if len(nums) == 0 {
    return nil
  }
  root := &TreeNode{Val: nums[0]}
  Queue := []*TreeNode{root}
  idx := 1
  for idx < len(nums) {
    node := Queue[0]
    Queue = Queue[1:]
    if nums[idx] != null {
      node.Left = &TreeNode{Val: nums[idx]}
      Queue = append(Queue, node.Left)
    }
    idx++
    if idx < len(nums) && nums[idx] != null {
      node.Right = &TreeNode{Val: nums[idx]}
      Queue = append(Queue, node.Right)
    }
    idx++
  }
  return root
}
func main() {
  nums := []int{5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1}
  root := buildTree(nums)
  fmt.Println(hasPathSum(root, 22))
  nums2 := []int{1, 2, 3}
  root = buildTree(nums2)
  fmt.Println(hasPathSum(root, 5))
  nums3 := []int{}
  root = buildTree(nums3)
  fmt.Println(hasPathSum(root, 0))
}

输出：

true

false

113. 路径总和 II Path Sum II

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22

输出：[[5,4,11,2],[5,8,4,5]]

示例 2：

输入：root = [1,2,3], targetSum = 5

输出：[]

示例 3：

输入：root = [1,2], targetSum = 0

输出：[]

提示：

树中节点总数在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

代码1：

package main
import (
  "fmt"
)
const null = -1 << 31
type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}
func pathSum(root *TreeNode, targetSum int) [][]int {
  res := [][]int{}
  sum := func(arr []int) int {
    res := 0
    for i := 0; i < len(arr); i++ {
      res += arr[i]
    }
    return res
  }
  for _, path := range binaryTreePaths(root) {
    if sum(path) == targetSum {
      res = append(res, append([]int{}, path...))
    }
  }
  return res
}
func binaryTreePaths(root *TreeNode) [][]int {
  res := [][]int{}
  if root == nil {
    return res
  }
  if root.Left == nil && root.Right == nil {
    return [][]int{{root.Val}}
  }
  leftPaths := binaryTreePaths(root.Left)
  rightPaths := binaryTreePaths(root.Right)
  paths := make([][]int, 0)
  for _, path := range leftPaths {
    paths = append(paths, append([]int{root.Val}, path...))
  }
  for _, path := range rightPaths {
    paths = append(paths, append([]int{root.Val}, path...))
  }
  return paths
}
func buildTree(nums []int) *TreeNode {
  if len(nums) == 0 {
    return nil
  }
  root := &TreeNode{Val: nums[0]}
  Queue := []*TreeNode{root}
  idx := 1
  for idx < len(nums) {
    node := Queue[0]
    Queue = Queue[1:]
    if nums[idx] != null {
      node.Left = &TreeNode{Val: nums[idx]}
      Queue = append(Queue, node.Left)
    }
    idx++
    if idx < len(nums) && nums[idx] != null {
      node.Right = &TreeNode{Val: nums[idx]}
      Queue = append(Queue, node.Right)
    }
    idx++
  }
  return root
}
func main() {
  nums := []int{5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1}
  root := buildTree(nums)
  fmt.Println(pathSum(root, 22))
  nums2 := []int{1, 2, 3}
  root = buildTree(nums2)
  fmt.Println(pathSum(root, 5))
  nums3 := []int{1, 2}
  root = buildTree(nums3)
  fmt.Println(pathSum(root, 0))
}

输出：

[[5 4 11 2] [5 8 4 5]]

[]

以上两题都用到了遍历出所有路径的函数 func binaryTreePaths(root *TreeNode) [][]int

package main
import (
  "fmt"
)
const null = -1 << 31
type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}
func binaryTreePaths(root *TreeNode) [][]int {
  res := [][]int{}
  if root == nil {
    return res
  }
  if root.Left == nil && root.Right == nil {
    return [][]int{{root.Val}}
  }
  leftPaths := binaryTreePaths(root.Left)
  rightPaths := binaryTreePaths(root.Right)
  paths := make([][]int, 0)
  for _, path := range leftPaths {
    paths = append(paths, append([]int{root.Val}, path...))
  }
  for _, path := range rightPaths {
    paths = append(paths, append([]int{root.Val}, path...))
  }
  return paths
}
func buildTree(nums []int) *TreeNode {
  if len(nums) == 0 {
    return nil
  }
  root := &TreeNode{Val: nums[0]}
  Queue := []*TreeNode{root}
  idx := 1
  for idx < len(nums) {
    node := Queue[0]
    Queue = Queue[1:]
    if nums[idx] != null {
      node.Left = &TreeNode{Val: nums[idx]}
      Queue = append(Queue, node.Left)
    }
    idx++
    if idx < len(nums) && nums[idx] != null {
      node.Right = &TreeNode{Val: nums[idx]}
      Queue = append(Queue, node.Right)
    }
    idx++
  }
  return root
}
func main() {
  nums := []int{5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1}
  root := buildTree(nums)
  fmt.Println(binaryTreePaths(root))
}

输出：

[[5 4 11 7] [5 4 11 2] [5 8 13] [5 8 4 5] [5 8 4 1]]

方法2： 递归 DFS

package main
import "fmt"
const null = -1 << 31 // 用Math.MinInt32来表示空节点
type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}
func buildTree(nums []int) *TreeNode {
  if len(nums) == 0 {
    return nil
  }
  root := &TreeNode{Val: nums[0]}
  Queue := []*TreeNode{root}
  idx := 1
  for idx < len(nums) {
    node := Queue[0]
    Queue = Queue[1:]
    if nums[idx] != null {
      node.Left = &TreeNode{Val: nums[idx]}
      Queue = append(Queue, node.Left)
    }
    idx++
    if idx < len(nums) && nums[idx] != null {
      node.Right = &TreeNode{Val: nums[idx]}
      Queue = append(Queue, node.Right)
    }
    idx++
  }
  return root
}
func pathSum(root *TreeNode, targetSum int) [][]int {
  result := [][]int{}
  if root == nil {
    return result
  }
  path := []int{}
  dfs(root, targetSum, path, &result)
  return result
}
func dfs(node *TreeNode, targetSum int, path []int, res *[][]int) {
  if node == nil {
    return
  }
  path = append(path, node.Val)
  if node.Left == nil && node.Right == nil && node.Val == targetSum {
    temp := make([]int, len(path))
    copy(temp, path)
    *res = append(*res, temp)
    return
  }
  dfs(node.Left, targetSum-node.Val, path, res)
  dfs(node.Right, targetSum-node.Val, path, res)
  path = path[:len(path)-1]
}
func main() {
  nums := []int{5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1}
  root := buildTree(nums)
  fmt.Println(pathSum(root, 22))
  nums2 := []int{1, 2, 3}
  root = buildTree(nums2)
  fmt.Println(pathSum(root, 5))
  nums3 := []int{1, 2}
  root = buildTree(nums3)
  fmt.Println(pathSum(root, 0))
}

114. 二叉树展开为链表 Flatten Binary Tree to Linked-list

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。

展开后的单链表应该与二叉树先序遍历顺序相同。

示例 1：

输入：root = [1,2,5,3,4,null,6]

输出：[1,null,2,null,3,null,4,null,5,null,6]

示例 2：

输入：root = []

输出：[]

示例 3：

输入：root = [0]

输出：[0]

提示：

树中结点数在范围 [0, 2000] 内

-100 <= Node.val <= 100

进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？

代码：

func flatten(root *TreeNode) {
list, cur := []int{}, &TreeNode{}
preorder(root, &list)
cur = root
for i := 1; i < len(list); i++ {
cur.Left = nil
cur.Right = &TreeNode{Val: list[i], Left: nil, Right: nil}
cur = cur.Right
}
return
}
func flatten1(root *TreeNode) {
if root == nil || (root.Left == nil && root.Right == nil) {
return
}
flatten(root.Left)
flatten(root.Right)
currRight := root.Right
root.Right = root.Left
root.Left = nil
for root.Right != nil {
root = root.Right
}
root.Right = currRight
}