目录

106. 从中序与后序遍历序列构造二叉树　Construct-binary-tree-from-inorder-and-postorder-traversal  🌟🌟

107. 二叉树的层序遍历 II  Binary Tree Level-order Traversal II  🌟🌟

108. 将有序数组转换为二叉搜索树 Convert SortedArray To BinarySearchTree  🌟

🌟 每日一练刷题专栏 🌟

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

106. 从中序与后序遍历序列构造二叉树　Construct-binary-tree-from-inorder-and-postorder-traversal

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

示例 2:

输入：inorder = [-1], postorder = [-1]
输出：[-1]

提示:

• 1 <= inorder.length <= 3000
• postorder.length == inorder.length
• -3000 <= inorder[i], postorder[i] <= 3000
• inorder 和 postorder 都由 不同 的值组成
• postorder 中每一个值都在 inorder 中
• inorder 保证是树的中序遍历
• postorder 保证是树的后序遍历

代码： 递归

package mainimport ("fmt"
)const null = -1 << 31type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}func buildTree(inorder []int, postorder []int) *TreeNode {if len(inorder) == 0 {return nil}rootVal := postorder[len(postorder)-1]root := &TreeNode{Val: rootVal}i := 0for ; i < len(inorder); i++ {if inorder[i] == rootVal {break}}root.Left = buildTree(inorder[:i], postorder[:i])root.Right = buildTree(inorder[i+1:], postorder[i:len(postorder)-1])return root
}func LevelOrder(root *TreeNode) [][]int {if root == nil {return [][]int{}}res := [][]int{}queue := []*TreeNode{root}level := 0for 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() {inorder := []int{9, 3, 15, 20, 7}postorder := []int{9, 15, 7, 20, 3}root := buildTree(inorder, postorder)fmt.Println(LevelOrder(root))
}

输出：

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

107. 二叉树的层序遍历 II  Binary Tree Level-order Traversal II

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

示例 1：

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

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

• 树中节点数目在范围 [0, 2000] 内
• -1000 <= Node.val <= 1000

代码1：  BFS

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

输出：

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

代码2：  DFS

package mainimport ("fmt"
)const null = -1 << 31type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}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 levelOrderBottom(root *TreeNode) [][]int {if root == nil {return nil}var res [][]intdfs(root, 0, &res)reverse(res)return res
}func dfs(node *TreeNode, depth int, res *[][]int) {if node == nil {return}if depth == len(*res) {*res = append(*res, []int{})}(*res)[depth] = append((*res)[depth], node.Val)dfs(node.Left, depth+1, res)dfs(node.Right, depth+1, res)
}func reverse(res [][]int) {i, j := 0, len(res)-1for i < j {res[i], res[j] = res[j], res[i]i++j--}
}func main() {nums := []int{3, 9, 20, null, null, 15, 7}root := buildTree(nums)fmt.Println(levelOrderBottom(root))
}

代码3：  BFS + Queue

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

108. 将有序数组转换为二叉搜索树 Convert SortedArray To BinarySearchTree

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 按 严格递增 顺序排列

代码1：

package mainimport ("fmt""strconv"
)const null = -1 << 31type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}func sortedArrayToBST(nums []int) *TreeNode {if len(nums) == 0 {return nil}return &TreeNode{Val: nums[len(nums)/2],Left:  sortedArrayToBST(nums[:len(nums)/2]),Right: sortedArrayToBST(nums[len(nums)/2+1:])}
}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}root := sortedArrayToBST(nums)fmt.Println(levelOrder(root))nums2 := []int{1, 3}root = sortedArrayToBST(nums2)fmt.Println(levelOrder(root))
}

输出：

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

代码2：

package mainimport ("fmt""strconv"
)const null = -1 << 31type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}func sortedArrayToBST(nums []int) *TreeNode {return buildBST(nums, 0, len(nums)-1)
}func buildBST(nums []int, left, right int) *TreeNode {if left > right {return nil}mid := (left + right) / 2root := &TreeNode{}root.Left = buildBST(nums, left, mid-1)root.Val = nums[mid]root.Right = buildBST(nums, mid+1, right)return root
}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}root := sortedArrayToBST(nums)fmt.Println(levelOrder(root))nums2 := []int{1, 3}root = sortedArrayToBST(nums2)fmt.Println(levelOrder(root))
}

输出：

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

🌟 每日一练刷题专栏 🌟

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

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

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

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

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

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

普通话学习