前置知识：无
建议：会同学可以跳过
二叉树的节点
type BinaryTreeNode[T any] struct {
Val T
Left *BinaryTreeNode
Right *BinaryTreeNode
}二叉树的先序、中序、后序
- 先序：“根左右”
- 中序：“左根右”
- 后序：“左右根”
任何一棵子树都要满足这个顺序
很好记，什么序是指“根”在哪
递归序加工出三种序的遍历
func recursiveOrder(root *BinaryTreeNode) {
if root == nil {
return
}
// 第一次访问 root
recursiveOrder(root.Left)
// 第二次访问 root
recursiveOrder(root.Right)
// 第三次访问 root
}递归序：在递归过程中，每一个非 nil 节点都会被访问 3 次！每次都操作（如：打印）的顺序
- 先序：每访问一个节点，第一次访问则进行操作（如：打印），第二次、第三次不操作
- 中序：第二次访问操作，第一次、第三次不操作
- 后序：第三次访问操作，第一次、第二次不操作
递归遍历二叉树复杂度分析
- 时间复杂度
O(n)- 一个非空节点访问三次
- 额外空间复杂度
O(h)，h是二叉树的高度- 递归的空间占用：递归过程中占用的系统调用栈的空间
- 最高会压到树高层的递归
备注
关于递归更多的内容会在【必备】课程里继续
二叉树更多更难的题会在【必备】课程里继续