繼續刷題

按照慣例，請ChatGPT幫我根據學習範圍出題，二元樹、BST、Tree Sort、Quick Sort、Merge Sort主題的LeetCode題目，包含15題簡單和5題中等的難度：

簡單題 (15題)

• Binary Tree Inorder Traversal - LeetCode 94
• Binary Tree Preorder Traversal - LeetCode 144
• Binary Tree Postorder Traversal - LeetCode 145
• Invert Binary Tree - LeetCode 226
• Symmetric Tree - LeetCode 101
• Maximum Depth of Binary Tree - LeetCode 104
• Same Tree - LeetCode 100
• Balanced Binary Tree - LeetCode 110
• Minimum Depth of Binary Tree - LeetCode 111
• Convert Sorted Array to Binary Search Tree - LeetCode 108
• Search in a Binary Search Tree - LeetCode 700
• Insert into a Binary Search Tree - LeetCode 701
• Binary Tree Paths - LeetCode 257
• Range Sum of BST - LeetCode 938
• Find Mode in Binary Search Tree - LeetCode 501

中等題 (5題)

• Validate Binary Search Tree - LeetCode 98
• Kth Smallest Element in a BST - LeetCode 230
• Construct Binary Tree from Preorder and Inorder Traversal - LeetCode 105
• Flatten Binary Tree to Linked List - LeetCode 114
• Binary Tree Zigzag Level Order Traversal - LeetCode 103

因為已經將本週的進度學習完了，所以這週剩下的時間就把以上題目做完，遇到以前做過的跳過。

這週，我已經順利完成了所有學習計劃，感覺自己又朝目標邁進了一大步！在筆記過程中，我重新整理了二元樹、BST、Tree Sort、Quick Sort、Merge Sort等核心概念，確保自己對這些主題有了更深的理解，接下來的時間用來專注的解決LeetCode上的題目，進一步鞏固我的知識和技能。

144. Binary Tree Preorder Traversal

標準的二元樹Preorder Traversal，前面已經完全學會用遞迴解題了。

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        output = []

        if not root:
            return []

        def dfs(output, node):
            if not node:
                return
            output.append(node.val)
            dfs(output, node.left)
            dfs(output, node.right)

        dfs(output, root)
        return output

發現有更簡化的方法：

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def dfs(node):
            if not node:
                return []
            return [node.val] + dfs(node.left) + dfs(node.right)

        return dfs(root)

145. Binary Tree Postorder Traversal

標準的二元樹Postorder Traversal。

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        output = []

        if not root:
            return []

        def dfs(output, node):
            if not node:
                return
            dfs(output, node.left)
            dfs(output, node.right)
            output.append(node.val)

        dfs(output, root)
        return output

簡化的版本：

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def dfs(node):
            if not node:
                return []
            return dfs(node.left) + dfs(node.right) + [node.val]

        return dfs(root)

98. Validate Binary Search Tree

判定輸入是否為BST的格式，正確返回Ture，反之則False
一開始一為只要判定當前節點與左右節點就可以了，後來才想到二元搜索樹的要求是左子樹中的所有節點值必須小於當前節點，因此單純比較當前節點與它的左、右節點是不夠的。
錯誤的程式碼：

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:

        def dfs(node):
            if not node:
                return
            dfs(node.left)
            if node.left and node.val <= node.left.val:
                return False
            if node.right and node.val >= node.right.val:
                return False
            dfs(node.right)

        return dfs(root)

正確的程式碼：

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def dfs(node, lower=float('-inf'), upper=float('inf')):
            if not node:
                return True

            # 如果當前節點值不在合法範圍內，返回 False
            if node.val <= lower or node.val >= upper:
                return False

            # 遞迴檢查左子樹，左子樹的所有節點值必須小於當前節點值
            # 遞迴檢查右子樹，右子樹的所有節點值必須大於當前節點值
            return dfs(node.left, lower, node.val) and dfs(node.right, node.val, upper)

        return dfs(root)