LeetCode刷題的Golang小技巧｜探索Tree解法

＊＊＊＊＊＊

這個系列是紀錄個人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 遞迴遍歷樹的左子樹和右子樹，並在過程中累加節點數值。

1. 每次進入新的節點時，累積當前的數值。
2. 若遇到 Leaf 節點，將該數值加總。
3. 若節點為空則回傳 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 層級遍歷樹，每層從左到右訪問所有節點，最後一層的最左側節點即為答案。

1. 使用 queue 來存放當前層的節點。
2. 每次取出節點時，先放入右節點再放入左節點，確保最後取出的節點是最底層最左側的節點。

/**
* 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 個節點時即為答案。

1. 使用遞迴或 stack 進行 inorder 遍歷。
2. 記錄當前已訪問的節點數量。
3. 當訪問到第 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 的問題，提升解題能力。