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
}