＊＊＊＊＊＊
這個系列是紀錄個人Leetcode刷題的心得，因為Leetcode題目背後都有要考的核心演算法，若是刷題前能夠熟悉演算法，對於解題會很有幫助！
＊＊＊＊＊＊在 Leetcode 的解題過程中，Binary Tree 是一個常見的數據結構，透過不同的遍歷方式可以解決各式各樣的問題。
針對Tree的題目，可以簡單總結三種狀況：
(1) 由上往下探索：使用「深度優先搜尋（DFS）」。
(2) 由左而右逐層探索：使用「廣度優先搜尋（BFS）」。
(3) 由小而大探索：使用「中序遍歷（Inorder Traversal）」。
1. 深度優先搜尋（DFS）- 使用遞迴
※ 觀念：深度優先搜索（DFS）是一種圖或樹的遍歷算法，它從根節點開始，沿著每一條分支深入到盡可能遠的節點，然後回溯並繼續探索其他分支。DFS 使用遞迴或堆疊（Stack）來實現這種深度遍歷。
※ 範例題目：Leetcode 129. Sum Root to Leaf Numbers
- 問題描述： 給定一棵二元樹，每條從 Root 到 Leaf 的路徑代表一個數字，請計算所有路徑數字的總和。
- 解法： 使用 DFS 遞迴遍歷樹的左子樹和右子樹，並在過程中累加節點數值。
- 每次進入新的節點時，累積當前的數值。
- 若遇到 Leaf 節點，將該數值加總。
- 若節點為空則回傳 0。
/**ㄟ
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sumNumbers(root *TreeNode) int {
return dfs(root, 0)
}
func dfs (node *TreeNode, input int) int {
if node == nil {
return 0
}
currentSum := 10 * input + node.Val
if node.Left == nil && node.Right == nil {
return currentSum
}
return dfs(node.Left, currentSum) + dfs(node.Right, currentSum)
}
2. 廣度優先搜尋（BFS）- 使用 Queue
※ 觀念：廣度優先搜索（BFS）是一種圖或樹的遍歷算法，它從根節點開始，首先訪問所有相鄰的節點，然後再訪問這些相鄰節點的相鄰節點，依此類推。BFS 使用隊列（Queue）來實現這種層次遍歷。
※ 範例題目：Leetcode 513. Find Bottom Left Tree Value
- 問題描述： 找出二元樹中最底層、最左側的節點值。
- 解法： 使用 BFS 層級遍歷樹，每層從左到右訪問所有節點，最後一層的最左側節點即為答案。
- 使用 queue 來存放當前層的節點。
- 每次取出節點時，先放入右節點再放入左節點，確保最後取出的節點是最底層最左側的節點。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findBottomLeftValue(root *TreeNode) int {
if root == nil {
return 0
}
queue := []*TreeNode{root}
result := 0
for len(queue) > 0 {
leng := len(queue)
result = queue[0].Val
for i := 0; i < leng; i++ {
node := queue[0]
queue = queue[1:]
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
}
return result
}
3. 中序遍歷（Inorder Traversal）
※ 觀念：inorder 是一種遍歷二元樹的方法，稱為中序遍歷（Inorder Traversal）。在中序遍歷中，節點的訪問順序是：先訪問左子樹，再訪問根節點，最後訪問右子樹。這種遍歷方式特別適用於二元搜索樹（BST），因為它會按升序訪問節點。
※ 範例題目：Leetcode 230. Kth Smallest Element in a BST
- 問題描述： 找出二元搜尋樹（BST）中第 K 小的元素。
- 解法： 中序遍歷 BST 會按照遞增順序拜訪節點，因此可以用 inorder 方式遍歷，當訪問到第 K 個節點時即為答案。
- 使用遞迴或 stack 進行 inorder 遍歷。
- 記錄當前已訪問的節點數量。
- 當訪問到第 K 個節點時，直接回傳該節點的值。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func kthSmallest(root *TreeNode, k int) int {
count := 0
result := 0
inorder(root, k, &count, &result)
return result
}
func inorder(node *TreeNode, k int, count *int, result *int) {
if node == nil {
return
}
inorder(node.Left, k, count, result)
*count++
if k == *count {
*result = node.Val
return
}
inorder(node.Right, k, count, result)
}
總結
Binary Tree 的遍歷方式主要包括 DFS（深度優先）、BFS（廣度優先）以及 Inorder（中序遍歷）。不同的問題可以透過不同的遍歷方法來有效解決，例如：
- DFS 遞迴 適用於由上往下的拜訪、累積計算（如 Sum Root to Leaf Numbers）。
- BFS 層級遍歷 適用於由左而右的拜訪、按層尋找節點（如 Find Bottom Left Tree Value）。
- Inorder 遍歷 特別適用於 BST 中的排序問題（如 Kth Smallest Element in a BST）。
透過熟悉這些遍歷方法，可以更靈活地應對各種 Binary Tree 的問題，提升解題能力。
