111. Minimum Depth of Binary Tree

題目要求我們找到二元樹的最小深度。

而最小深度的定義是：
從根節點到最近葉子節點的最短路徑上的節點數目。
葉子節點是沒有子節點的節點，也就是說，它沒有左子節點和右子節點。

程式碼：

class Solution:
    def minDepth(self, root):
        # 如果根節點是空的，返回 0
        if not root:
            return 0

        # 如果是葉子節點，返回 1
        if not root.left and not root.right:
            return 1

        # 如果左子樹或右子樹是空的，取非空的子樹的最小深度
        if not root.left:
            return self.minDepth(root.right) + 1
        if not root.right:
            return self.minDepth(root.left) + 1

        # 如果左右子樹都存在，取左右子樹中較小的深度
        return min(self.minDepth(root.left), self.minDepth(root.right)) + 1

230. Kth Smallest Element in a BST

題目要求我們在一棵**二元搜尋樹（BST, Binary Search Tree）**中找到第 k 小的節點值。

二元搜尋樹的特點：
左子樹的所有節點值都小於根節點的值。
右子樹的所有節點值都大於根節點的值。
中序遍歷（In-order traversal）可以將二元搜尋樹的節點按升序排序。

解題方法

因為BST使用中序遍歷會按照從小到大的順序訪問節點，所以找出第 k 小的數值，就會是第 k 個數值。

程式碼：

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        self.counter = 0

        def dfs(node):
            if not node:
                return None
            
            # 遍歷左子樹，檢查是否找到了結果
            left = dfs(node.left)
            if left is not None:
                return left
            
            # 計數器加1，表示已經遍歷了一個節點
            self.counter += 1
            
            # 當計數器等於 k 時，返回當前節點值
            if self.counter == k:
                return node.val
            
            # 遍歷右子樹，檢查是否找到了結果
            return dfs(node.right)

        # 從根節點開始進行 DFS 遍歷，並返回結果
        return dfs(root)

與普通的中序遍歷的最大區別

1. 計數：
   在這個問題中，除了使用中序遍歷，我們還必須計數我們遍歷的節點數，因為我們需要找到第 k 小的節點。
   每遍歷一個節點時，我們都會增加計數器，並檢查這個計數是否等於 k。當計數器等於 k 時，說明我們已經找到了答案。
2. 及時返還：
   與普通中序遍歷不同，我們不會一直遍歷整棵樹。在找到第 k 小的節點後，我們會立即返還結果，並停止後續的遍歷。
   具體來說，我們在遍歷左子樹或右子樹後，會檢查結果是否已經找到了。如果已經找到（即非 None），就不再繼續遞迴，直接返回結果。