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

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

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

🌟 每日一练刷题专栏 🌟

Golang每日一练专栏

Python每日一练专栏

C/C++每日一练专栏

Java每日一练专栏

二叉树专题（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 mainimport ("fmt"
)const null = -1 << 31type TreeNode struct {Val   intLeft  *TreeNodeRight *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 := 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(zigzagLevelOrder(root))
}

代码2：迭代

package mainimport ("fmt"
)const null = -1 << 31type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}func zigzagLevelOrder(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 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 := 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(zigzagLevelOrder(root))
}

输出：

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

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

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

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

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

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

    3/ \9  20/  \15   7

返回它的最大深度 3 。

代码1：递归

package mainimport ("fmt"
)const null = -1 << 31type TreeNode struct {Val   intLeft  *TreeNodeRight *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 := 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(maxDepth(root))
}

代码2：迭代

package mainimport ("fmt"
)const null = -1 << 31type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}func maxDepth(root *TreeNode) int {if root == nil {return 0}depth := 0queue := []*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 := 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(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 mainimport ("fmt"
)const null = -1 << 31type TreeNode struct {Val   intLeft  *TreeNodeRight *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) *TreeNodebuild = func(preStart, preEnd, inStart, inEnd int) *TreeNode {if preStart > preEnd {return nil}rootVal := preorder[preStart]rootIndex := index[rootVal]leftSize := rootIndex - inStartrightSize := inEnd - rootIndexleft := 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 := 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() {preorder := []int{3, 9, 20, 15, 7}inorder := []int{9, 3, 15, 20, 7}root := buildTree(preorder, inorder)fmt.Println(LevelOrder(root))
}

输出：

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