226. Invert Binary Tree

題目描述得非常簡單，給定一棵二元樹，你需要翻轉它，將左子樹與右子樹互換，輸出這棵樹翻轉後的結果。
使用遞迴的解法：

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return None
            # 交換左右子樹
        root.left, root.right = root.right, root.left
        # 遞迴對左右子樹進行翻轉
        self.invertTree(root.left)
        self.invertTree(root.right)

        return root

使用queue的解法：

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root is None:
            return None

        queue = deque([root])

        while queue:
            current = queue.popleft()

            # 交換左右子樹
            current.left, current.right = current.right, current.left

            # 將左右子樹節點加入隊列中
            if current.left:
                queue.append(current.left)
            if current.right:
                queue.append(current.right)

        return root

110. Balanced Binary Tree

給定一棵二元樹，請你判斷它是否是高度平衡的。
這邊要講到一棵平衡二元樹的定義，一棵二元樹中的每個節點，左右子樹的高度差不能超過 1。
舉例以下：

輸入：
    3
   / \
  9  20
    /  \
   15   7

輸出：True
這棵樹是平衡的，因為每個節點的左右子樹高度差都不超過 1。

輸入：
    1
   / \
  2   2
 / \
3   3
/ \
4   4

輸出：False
這棵樹不平衡，因為在節點 1，左右子樹的高度差為 2。

解法思路

我們要需要計算每個節點的高度，並在計算高度的同時，檢查每個節點的左右子樹高度差是否超過 1。如果任一節點的左右子樹高度差超過 1，則這棵樹不是平衡樹。

1. 定義一個遞迴函數，用來計算每個節點的高度。
2. 在計算高度時，檢查左右子樹是否平衡。如果子樹不平衡，則直接返回 -1 表示不平衡；如果平衡，則返回這個節點的高度。
3. 在根節點處調用這個函數，根據返回值判斷樹是否平衡。

程式碼：

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def check_height(node: TreeNode) -> int:
            if node is None:
                return 0  # 空節點的高度為 0

            # 計算左子樹的高度
            left_height = check_height(node.left)
            if left_height == -1:
                return -1  # 左子樹不平衡，提前結束

            # 計算右子樹的高度
            right_height = check_height(node.right)
            if right_height == -1:
                return -1  # 右子樹不平衡，提前結束

            # 如果左右子樹的高度差超過 1，返回 -1 表示不平衡
            if abs(left_height - right_height) > 1:
                return -1

            # 否則返回當前節點的高度
            return max(left_height, right_height) + 1

        # 使用 check_height 函數檢查整棵樹是否平衡
        return self.check_height(root) != -1