二叉树专题（4）

103. 二叉树的锯齿形层序遍历 Binary Tree Zigzag Level Order Traversal

给你二叉树的根节点 root ，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例 1：

输入：root = [3,9,20,null,null,15,7]

输出：[[3],[20,9],[15,7]]

示例 2：

输入：root = [1]

输出：[[1]]

示例 3：

输入：root = []

输出：[]

提示：

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

-100 <= Node.val <= 100

代码1：递归

package main
import (
  "fmt"
)
const null = -1 << 31
type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}
func zigzagLevelOrder(root *TreeNode) [][]int {
  res := [][]int{}
  dfs(root, 0, &res)
  return res
}
func dfs(node *TreeNode, level int, res *[][]int) {
  if node == nil {
    return
  }
  if len(*res) <= level {
    *res = append(*res, []int{})
  }
  if level%2 == 0 {
    (*res)[level] = append((*res)[level], node.Val)
  } else {
    (*res)[level] = append([]int{node.Val}, (*res)[level]...)
  }
  dfs(node.Left, level+1, res)
  dfs(node.Right, level+1, res)
}
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{3, 9, 20, null, null, 15, 7}
  root := buildTree(nums)
  fmt.Println(zigzagLevelOrder(root))
}

代码2：迭代

package main
import (
  "fmt"
)
const null = -1 << 31
type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}
func zigzagLevelOrder(root *TreeNode) [][]int {
  if root == nil {
    return [][]int{}
  }
  res := [][]int{}
  queue := []*TreeNode{root}
  level := 0
  for len(queue) > 0 {
    size := len(queue)
    levelRes := []int{}
    stack := []*TreeNode{}
    for i := 0; i < size; i++ {
      node := queue[0]
      queue = queue[1:]
      levelRes = append(levelRes, node.Val)
      if level%2 == 0 {
        if node.Left != nil {
          stack = append(stack, node.Left)
        }
        if node.Right != nil {
          stack = append(stack, node.Right)
        }
      } else {
        if node.Right != nil {
          stack = append(stack, node.Right)
        }
        if node.Left != nil {
          stack = append(stack, node.Left)
        }
      }
    }
    for i := len(stack) - 1; i >= 0; i-- {
      queue = append(queue, stack[i])
    }
    res = append(res, levelRes)
    level++
  }
  return res
}
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{3, 9, 20, null, null, 15, 7}
  root := buildTree(nums)
  fmt.Println(zigzagLevelOrder(root))
}

输出：

[[3] [20 9] [15 7]]

104. 二叉树的最大深度 Maximum Depth of Binary-tree]

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：

给定二叉树 [3,9,20,null,null,15,7]，

/ \

9 20

/ \

15 7

返回它的最大深度 3 。

代码1：递归

package main
import (
  "fmt"
)
const null = -1 << 31
type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}
func maxDepth(root *TreeNode) int {
  if root == nil {
    return 0
  }
  leftDepth := maxDepth(root.Left)
  rightDepth := maxDepth(root.Right)
  return max(leftDepth, rightDepth) + 1
}
func max(x, y int) int {
  if x > y {
    return x
  }
  return y
}
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{3, 9, 20, null, null, 15, 7}
  root := buildTree(nums)
  fmt.Println(maxDepth(root))
}

代码2：迭代

1.package main
import (
  "fmt"
)
const null = -1 << 31
type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}
func maxDepth(root *TreeNode) int {
  if root == nil {
    return 0
  }
  depth := 0
  queue := []*TreeNode{root}
  for len(queue) > 0 {
    size := len(queue)
    for i := 0; i < size; i++ {
      node := queue[0]
      queue = queue[1:]
      if node.Left != nil {
        queue = append(queue, node.Left)
      }
      if node.Right != nil {
        queue = append(queue, node.Right)
      }
    }
    depth++
  }
  return depth
}
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{3, 9, 20, null, null, 15, 7}
  root := buildTree(nums)
  fmt.Println(maxDepth(root))
}

输出：

105. 从前序与中序遍历序列构造二叉树 Construct-binary-tree-from-preorder-and-inorder-traversal

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]

输出: [-1]

提示:

1 <= preorder.length <= 3000

inorder.length == preorder.length

-3000 <= preorder[i], inorder[i] <= 3000

preorder 和 inorder 均无重复元素

inorder 均出现在 preorder

preorder 保证为二叉树的前序遍历序列

inorder 保证为二叉树的中序遍历序列

代码：

package main
import (
  "fmt"
)
const null = -1 << 31
type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}
func buildTree(preorder []int, inorder []int) *TreeNode {
  index := make(map[int]int)
  for i, val := range inorder {
    index[val] = i
  }
  var build func(preStart, preEnd, inStart, inEnd int) *TreeNode
  build = func(preStart, preEnd, inStart, inEnd int) *TreeNode {
    if preStart > preEnd {
      return nil
    }
    rootVal := preorder[preStart]
    rootIndex := index[rootVal]
    leftSize := rootIndex - inStart
    rightSize := inEnd - rootIndex
    left := build(preStart+1, preStart+leftSize, inStart, rootIndex-1)
    right := build(preEnd-rightSize+1, preEnd, rootIndex+1, inEnd)
    return &TreeNode{Val: rootVal, Left: left, Right: right}
  }
  return build(0, len(preorder)-1, 0, len(inorder)-1)
}
func LevelOrder(root *TreeNode) [][]int {
  if root == nil {
    return [][]int{}
  }
  res := [][]int{}
  queue := []*TreeNode{root}
  level := 0
  for len(queue) > 0 {
    size := len(queue)
    levelRes := []int{}
    stack := []*TreeNode{}
    for i := 0; i < size; i++ {
      node := queue[0]
      queue = queue[1:]
      levelRes = append(levelRes, node.Val)
      if node.Right != nil {
        stack = append(stack, node.Right)
      }
      if node.Left != nil {
        stack = append(stack, node.Left)
      }
    }
    for i := len(stack) - 1; i >= 0; i-- {
      queue = append(queue, stack[i])
    }
    res = append(res, levelRes)
    level++
  }
  return res
}
func main() {
  preorder := []int{3, 9, 20, 15, 7}
  inorder := []int{9, 3, 15, 20, 7}
  root := buildTree(preorder, inorder)
  fmt.Println(LevelOrder(root))
}