Golang每日一练(leetDay0037) 二叉树专题（6）

2023-05-28 155

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Golang每日一练(leetDay0037) 二叉树专题（6）

二叉树专题（6）

109. 有序链表转换二叉搜索树 Convert-sorted-list-to-binary-search-tree

给定一个单链表的头节点 head ，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差不超过 1。

示例 1:

输入: head = [-10,-3,0,5,9]

输出: [0,-3,9,-10,null,5]

解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。

示例 2:

输入: head = []

输出: []

提示:

head 中的节点数在[0, 2 * 10^4] 范围内

-10^5 <= Node.val <= 10^5

代码：

package main
import (
  "fmt"
  "strconv"
)
const null = -1 << 31
type ListNode struct {
  Val  int
  Next *ListNode
}
type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}
func sortedListToBST(head *ListNode) *TreeNode {
  var nodes []ListNode
  for head != nil {
    nodes = append(nodes, *head)
    head = head.Next
  }
  return builder(nodes, 0, len(nodes)-1)
}
func builder(nodes []ListNode, left, right int) *TreeNode {
  if left > right {
    return nil
  }
  mid := (left + right + 1) / 2
  root := &TreeNode{nodes[mid].Val, nil, nil}
  root.Left = builder(nodes, left, mid-1)
  root.Right = builder(nodes, mid+1, right)
  return root
}
func ArrayToList(list []int) *ListNode {
  head := &ListNode{Val: 0}
  for i := len(list) - 1; i >= 0; i-- {
    p := &ListNode{Val: list[i]}
    p.Next = head.Next
    head.Next = p
  }
  return head.Next
}
func levelOrder(root *TreeNode) string {
  if root == nil {
    return "[]"
  }
  arr := []int{}
  que := []*TreeNode{root}
  for len(que) > 0 {
    levelSize := len(que)
    for i := 0; i < levelSize; i++ {
      node := que[0]
      que = que[1:]
      if node == nil {
        arr = append(arr, null)
        continue
      }
      arr = append(arr, node.Val)
      que = append(que, node.Left, node.Right)
    }
  }
  size := len(arr)
  for size > 0 && arr[size-1] == null {
    arr = arr[:size-1]
    size = len(arr)
  }
  result := "["
  for i, n := range arr {
    if n == null {
      result += "null"
    } else {
      result += strconv.FormatInt(int64(n), 10)
    }
    if i < size-1 {
      result += ","
    } else {
      result += "]"
    }
  }
  return result
}
func main() {
  nums := []int{-10, -3, 0, 5, 9}
  head := ArrayToList(nums)
  root := sortedListToBST(head)
  fmt.Println(levelOrder(root))
  nums2 := []int{}
  head = ArrayToList(nums2)
  root = sortedListToBST(head)
  fmt.Println(levelOrder(root))
}

输出：

[0,-3,9,-10,null,5]

[]

110. 平衡二叉树 Balanced Binary Tree

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例 1：

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

输出：true

示例 2：

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

输出：false

示例 3：

输入：root = []

输出：true

提示：

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

-10^4 <= Node.val <= 10^4

代码：

package main
import (
  "fmt"
)
const null = -1 << 31
type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}
func isBalanced(root *TreeNode) bool {
  if root == nil {
    return true
  }
  leftHight := depth(root.Left)
  rightHight := depth(root.Right)
  return abs(leftHight-rightHight) <= 1 && isBalanced(root.Left) && isBalanced(root.Right)
}
func depth(root *TreeNode) int {
  if root == nil {
    return 0
  }
  return max(depth(root.Left), depth(root.Right)) + 1
}
func abs(x int) int {
  if x < 0 {
    return -x
  }
  return x
}
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(isBalanced(root))
  nums2 := []int{1, 2, 2, 3, 3, null, null, 4, 4}
  root = buildTree(nums2)
  fmt.Println(isBalanced(root))
  nums3 := []int{}
  root = buildTree(nums3)
  fmt.Println(isBalanced(root))
}

输出：

true

false

true

111. 二叉树的最小深度 Minimum Depth of Binary Tree

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

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

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

示例 1：

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

输出：2

示例 2：

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

输出：5

提示：

树中节点数的范围在 [0, 10^5] 内

-1000 <= Node.val <= 1000

代码：

package main
import (
  "fmt"
)
const null = -1 << 31
type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}
func minDepth(root *TreeNode) int {
  if root == nil {
    return 0
  }
  if root.Left == nil {
    return minDepth(root.Right) + 1
  }
  if root.Right == nil {
    return minDepth(root.Left) + 1
  }
  return min(minDepth(root.Left), minDepth(root.Right)) + 1
}
func min(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(minDepth(root))
  nums2 := []int{2, null, 3, null, 4, null, 5, null, 6}
  root = buildTree(nums2)
  fmt.Println(minDepth(root))
}