目录

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

110. 平衡二叉树 Balanced Binary Tree  🌟

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

🌟 每日一练刷题专栏 🌟

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

二叉树专题（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 mainimport ("fmt""strconv"
)const null = -1 << 31type ListNode struct {Val  intNext *ListNode
}type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}func sortedListToBST(head *ListNode) *TreeNode {var nodes []ListNodefor 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) / 2root := &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.Nexthead.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 mainimport ("fmt"
)const null = -1 << 31type TreeNode struct {Val   intLeft  *TreeNodeRight *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 := 1for 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 mainimport ("fmt"
)const null = -1 << 31type TreeNode struct {Val   intLeft  *TreeNodeRight *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 := 1for 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))
}

输出：

2
5

🌟 每日一练刷题专栏 🌟

✨ 持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！ 

🌟 收藏，你的青睐是我努力的方向！ 

✎ 评论，你的意见是我进步的财富！  

☸ 主页：https://hannyang.blog.csdn.net/ 

	Golang每日一练 专栏
	Python每日一练 专栏
	C/C++每日一练 专栏
	Java每日一练 专栏