首页 计算机科学 算法训练 2023

# 二叉树遍历

# 遍历

# 递归实现

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/06_BinaryTree/level_1/topic_1.go

// 前序遍历
func (root *TreeNode) PreOrderTraversal() {
	if root == nil {
		return
	}
	fmt.Println(root.Val)
	root.Left.PreOrderTraversal()
	root.Right.PreOrderTraversal()
}
// 中序遍历
func (root *TreeNode) InOrderTraversal() {
	if root == nil {
		return
	}
	root.Left.InOrderTraversal()
	fmt.Println(root.Val)
	root.Right.InOrderTraversal()
}
// 后序遍历
func (root *TreeNode) PostOrderTraversal() {
	if root == nil {
		return
	}
	root.Right.PostOrderTraversal()
	root.Left.PostOrderTraversal()
	fmt.Println(root.Val)
}
# 迭代实现
https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/06_BinaryTree/level_1/topic_3.go
// 迭代法实现二叉树遍历
// 前序遍历
func (root *TreeNode) IteratePreOrderTraversal() {
	if root == nil {
		return
	}
	ans := []int{}
	stack := []*TreeNode{root}
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		// 前序
		ans = append(ans, node.Val)
		if node.Right != nil {
			stack = append(stack, node.Right)
		}
		if node.Left != nil {
			stack = append(stack, node.Left)
		}
	}
	fmt.Println(ans)
}
// 前序遍历
func (root *TreeNode) IteratePreOrderTraversalV2() {
	if root == nil {
		return
	}
	ans := []int{}
	stack := []*TreeNode{}
	curr := root
	for len(stack) > 0 || curr != nil {
		for curr != nil {
			ans = append(ans, curr.Val)
			stack = append(stack, curr)
			curr = curr.Left
		}
		curr = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		curr = curr.Right
	}
	fmt.Println(ans)
}
// 中序遍历
func (root *TreeNode) IterateInOrderTraversal() {
	if root == nil {
		return
	}
	ans := []int{}
	stack := []*TreeNode{}
	curr := root
	for len(stack) > 0 || curr != nil {
		for curr != nil {
			stack = append(stack, curr)
			curr = curr.Left
		}
		curr = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		ans = append(ans, curr.Val)
		curr = curr.Right
	}
	fmt.Println(ans)
}
// 后序遍历
func (root *TreeNode) IteratePostOrderTraversal() {
	if root == nil {
		return
	}
	ans := []int{}
	stack := []*TreeNode{}
	curr := root
	for len(stack) > 0 || curr != nil {
		for curr != nil {
			ans = append(ans, curr.Val)
			stack = append(stack, curr)
			curr = curr.Left
		}
		curr = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		curr = curr.Right
	}
	// 前序遍历之后翻转一下就是后序
	for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
		ans[i], ans[j] = ans[j], ans[i]
	}
	fmt.Println(ans)
}
# 算法题
# 1. 从前序与中序遍历序列构造二叉树
https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/
https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/06_BinaryTree/level_1/topic_2.go
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
func buildTree(preorder []int, inorder []int) *TreeNode {
	if len(preorder) == 0 {
		return nil
	}
	root := &TreeNode{preorder[0], nil, nil}
	index := 0
	for index < len(inorder) {
		if inorder[index] == preorder[0] {
			break
		}
		index++
	}
	root.Left = buildTree(preorder[1:len(inorder[:index])+1], inorder[:index])
	root.Right = buildTree(preorder[len(inorder[:index])+1:], inorder[index+1:])
	return root
}
# 2. 二叉树的层序遍历
https://leetcode.cn/problems/binary-tree-level-order-traversal/description/
https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/06_BinaryTree/level_2/topic_1.go
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
func levelOrder(root *TreeNode) [][]int {
	ans := [][]int{}
	if root == nil {
		return ans
	}
	level := 0
	list := []*TreeNode{root}
	for len(list) > 0 {
		tempList := []*TreeNode{}
		ans = append(ans, []int{})
		for _, v := range list {
			ans[level] = append(ans[level], v.Val)
			if v.Left != nil {
				tempList = append(tempList, v.Left)
			}
			if v.Right != nil {
				tempList = append(tempList, v.Right)
			}
		}
		level++
		list = tempList
	}
	return ans
}
# 3. 在每个树行中找最大值
https://leetcode.cn/problems/find-largest-value-in-each-tree-row/description/
https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/06_BinaryTree/level_2/topic_2.go
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
func largestValues(root *TreeNode) []int {
	ans := []int{}
	if root == nil {
		return ans
	}
	list := []*TreeNode{root}
	for len(list) > 0 {
		maxVal := math.MinInt
		tempList := []*TreeNode{}
		for _, v := range list {
			if maxVal < v.Val {
				maxVal = v.Val
			}
			if v.Left != nil {
				tempList = append(tempList, v.Left)
			}
			if v.Right != nil {
				tempList = append(tempList, v.Right)
			}
		}
		ans = append(ans, maxVal)
		list = tempList
	}
	return ans
}
 
-->