二叉树定义和种类
二叉树是一种树形数据结构，其中每个节点最多有两个子节点，通常称为“左子节点”和“右子节点”。二叉树在计算机科学中有广泛的应用，比如表达式解析、排序算法、搜索算法等。
二叉树的定义
一个二叉树由一组节点组成，其中每个节点至多有两个子节点，分别称为左子节点和右子节点。二叉树可以是空的（没有节点），也可以是一个根节点加上两个分别是左子树和右子树的二叉树。
二叉树的种类
二叉树有多种不同的类型，每种类型都有其特定的性质和用途。常见的二叉树种类包括：
-
满二叉树（Full Binary Tree）：
- 每个节点要么是叶子节点，要么有两个子节点。
- 满二叉树的所有叶子节点都在同一层次上。
-
完全二叉树（Complete Binary Tree）：
- 所有层都是完全填满的，除了最后一层。
- 最后一层的节点尽可能靠左排列。
-
完美二叉树（Perfect Binary Tree）：
- 是一种特殊的满二叉树。
- 所有内部节点都有两个子节点，所有叶子节点都在同一层次上。
-
平衡二叉树（Balanced Binary Tree）：
- 任意节点的左子树和右子树的高度差不超过1。
- 例如：AVL树、红黑树。
-
二叉搜索树（Binary Search Tree, BST）：
- 对于每个节点，其左子树中所有节点的值都小于该节点的值，其右子树中所有节点的值都大于该节点的值。
- 允许高效的查找、插入和删除操作。
二叉树的表示
二叉树可以通过多种方式表示，常见的表示方法包括：
-
链式存储：
- 每个节点包含一个数据元素和两个指针，分别指向左子节点和右子节点。
type TreeNode struct { Val int Left *TreeNode Right *TreeNode } -
数组表示：
- 完全二叉树可以用数组表示，根节点存储在索引1的位置（或0），对于索引为 (i) 的节点，其左子节点存储在索引 (2i)（或 (2i+1)），右子节点存储在索引 (2i+1)（或 (2i+2)）。
// 数组表示的二叉树 tree := []int{1, 2, 3, 4, 5, 6, 7}
二叉树的遍历
二叉树的遍历是指按照某种顺序访问树中的每个节点。常见的遍历方法有：
- 前序遍历（Pre-order Traversal）：
- 访问根节点 -> 前序遍历左子树 -> 前序遍历右子树。
func preorderTraversal(root *TreeNode) []int { // 三种遍历顺序指的是根节点在“左右”两个节点中的顺序 // 前序遍历 根左右 // 中序遍历 左根右 // 后续遍历 左右根 var res []int var traversal func(node *TreeNode) traversal = func(node *TreeNode) { if node == nil { return } res = append(res,node.Val) traversal(node.Left) traversal(node.Right) } traversal(root) return res }func preorderTraversal(root *TreeNode) []int { // 考虑使用迭代法解决 根左右，所以先遍历根，然后入栈右左，实现出栈顺序是左右 if root == nil { return nil } st := list.New() // go包双向链表 var ans []int st.PushBack(root) for st.Len() > 0 { node := st.Remove(st.Back()).(*TreeNode) ans = append(ans, node.Val) if node.Right != nil { st.PushBack(node.Right) } if node.Left != nil { st.PushBack(node.Left) } } return ans } - 中序遍历（In-order Traversal）：
- 中序遍历左子树 -> 访问根节点 -> 中序遍历右子树。
func postorderTraversal(root *TreeNode) []int { var res []int traversal(root, &res) return res } func traversal(root *TreeNode, res *[]int) { if root == nil { return } traversal(root.Left, res) traversal(root.Right, res) *res = append(*res, root.Val) }func inorderTraversal(root *TreeNode) []int { // 中序迭代有点难理解的 if root == nil { return nil } var res []int st := list.New() cur := root for cur != nil || st.Len() > 0{ if cur != nil{ st.PushBack(cur) cur = cur.Left } else { cur = st.Remove(st.Back()).(*TreeNode) res = append(res, cur.Val) cur = cur.Right } } return res } - 后序遍历（Post-order Traversal）：
- 后序遍历左子树 -> 后序遍历右子树 -> 访问根节点。
func inorderTraversal(root *TreeNode) []int { res := []int{} traversal(root, &res) return res } func traversal(root *TreeNode, res *[]int) { if root == nil { return } traversal(root.Left, res) *res = append(*res, root.Val) traversal(root.Right, res) }func postorderTraversal(root *TreeNode) []int { // 思路，左右中，反转之后就是中右左， 那么和前序遍历zhong左右只是区别在于入栈顺序，然后最终将res翻转即可 if root == nil { return nil } var res = []int{} st := list.New() st.PushBack(root) for st.Len() > 0 { node := st.Remove(st.Back()).(*TreeNode) res = append(res, node.Val) if node.Left != nil { st.PushBack(node.Left) } if node.Right != nil { st.PushBack(node.Right) } } return reverse(res) } func reverse(l []int) []int { left, right := 0, len(l) - 1 for left < right { l[left], l[right] = l[right], l[left] left++ right-- } return l } - 层次遍历（Level-order Traversal）：
- 按照层次从上到下、从左到右依次访问每个节点。
func levelOrder(root *TreeNode) [][]int { // 通过队列实现广度优先遍历 if root == nil { return nil } var res [][]int queue := list.New() // 同样使用go包双向链表实现队列，push = pushback pop = remove(front()) queue.PushBack(root) size := 1 // 对于每一层的遍历，都要维护一个size变量，方便记录弹出元素个数 for queue.Len() > 0{ var ( count int r []int ) for i := 0; i < size; i++ { // 对于每一层的遍历次数 // 1, 插入节点元素值 node := queue.Remove(queue.Front()).(*TreeNode) r = append(r, node.Val) // 左右子节点入队, 顺序不能颠倒，队列先入先出 if node.Left != nil { queue.PushBack(node.Left) count++ } if node.Right != nil { queue.PushBack(node.Right) count++ } } // 此时上一层已经遍历完成，将size赋值为下一层的节点数量 size = count res = append(res, r) } return res }
其中前序遍历，中序遍历，后序遍历都是深度优先遍历，通常采用递归方法实现，层序遍历为广度优先遍历，采用队列方法实现
深度优先搜索（DFS）和广度优先搜索（BFS）
深度优先搜索（DFS）和广度优先搜索（BFS）是两种基本的图遍历算法，它们也常用于树的遍历。以下是它们的详细介绍：
深度优先搜索（DFS）
深度优先搜索是一种优先探索尽可能深的节点的遍历策略。它沿着每一个分支尽可能深地搜索，直到不能再继续为止，然后回溯并继续探索下一个分支。DFS可以使用递归或显式的栈来实现。
广度优先搜索（BFS）
广度优先搜索是一种优先探索离起始节点最近的节点的遍历策略。它按层次逐层访问节点，先访问完一层的所有节点，再继续访问下一层的节点。BFS通常使用队列来实现。
DFS：
- 适用于需要遍历到某个特定深度的场景，例如解决迷宫问题、寻找路径等。
- 常用于图的连通性检测、拓扑排序等。
BFS：
- 适用于寻找最短路径的场景，例如在无权图中寻找两个节点之间的最短路径。
- 常用于层次遍历、广度优先搜索树等。