1、二叉树介绍
【1】核心概念
| 结构 | 含义 |
|---|---|
| 节点结构 | 二叉树由节点组成， 每个节点包含一个数据元素和最多两个子节点：左子节点和右子节点 |
| 根节点 | 树的顶部节点称为根节点，是访问整个树的起点 |
| 叶节点 | 没有子节点的节点成为叶节点 |
| 子树 | 每个节点及其后代构成一个子树 |
【2】关键特性
| 特性 | 含义 |
|---|---|
| 最大子节点数 | 每个节点最多有两个子节点 |
| 遍历方式 | 前序遍历（根-左-右） 中序遍历（左-根-右） 后序遍历（左-右-根） 层次遍历（按层从做到右） |
| 常见类型 | 二叉搜索树（BST）：左子树所有节点值小于根节点，右子树所有节点值大于根节点，用于高效搜索 平衡二叉树（AVL树）：自动保持树的高度平衡，确保操作效率 堆：用于优先队列，如最大堆和最小堆 |
2、算法题
【1】二叉树的前序遍历
LeetCode第144题，题目如下：
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[1,2,4,5,6,7,3,8,9]
示例 3：
输入：root = []
输出：[]
示例 4：
输入：root = [1]
输出：[1]
提示：
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
代码示例：
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
//递归解法
func preorderTraversal(root *TreeNode) []int {
//结果数组
result := make([]int, 0)
//定义递归函数
var traversal func(node *TreeNode)
traversal = func(node *TreeNode) {
if node == nil { //空节点直接退出
return
}
//前序遍历：根->左->右
//访问根节点
result = append(result, node.Val)
//递归左子树
traversal(node.Left)
//递归右子树
traversal(node.Right)
}
//从根节点开始遍历
traversal(root)
return result
}
【2】二叉树的后序遍历
LeetCode第145题，题目如下：
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[3,2,1]
示例 2：
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[4,6,7,5,2,9,8,3,1]
示例 3：
输入：root = []
输出：[]
示例 4：
输入：root = [1]
输出：[1]
提示：
树中节点的数目在范围 [0, 100] 内
-100 <= Node.val <= 100
代码示例：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func postorderTraversal(root *TreeNode) []int {
//递归终止条件：空节点返回空切片
if root == nil {
return []int{}
}
//递归遍历左子树
left := postorderTraversal(root.Left)
//递归便利右子树
right := postorderTraversal(root.Right)
//合并结果
//先拼接左右子树结果
result := append(left, right...)
//最后添加当前节点值
result = append(result, root.Val)
return result
}