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   intLeft  *TreeNodeRight *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
}