【Leetcode 筆記】104. Maximum Depth of Binary Tree

題目解釋

給定 binary tree 的 root，返回其最大深度。

Binary tree 的最大深度是從 root 到最遠 leaf node 的最長路徑上的 node 數。

範例

• 輸入: root = [3, 9, 20, null, null, 15, 7]
• 輸出: 3

root 到最遠且同層的 15 或 7 的節點數量都是 3。

最佳解法

在寫 Tree 的題目時，最重要的就是 遞迴 (Recursion) 的概念。

我們可以把這題拆解為

1. 遞迴的處理左子樹
2. 遞迴的處理右子樹
3. 回傳左右深度的最大值 + 1 (一定是多走了一層才會走到這)

說明

因為如果透過一個變數去記遞迴中的 depth 的話，不僅繁瑣還容易出錯，
我們索性將 return 的數值做為當前遞迴的最大 depth。

我們會不斷的先往左邊走，都 return 回根節點後再來才是向右走，
所以這是一種 深度優先探索 (DFS) 的演算法。

程式碼

拆的比較細的遞迴版

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        def _dfs(root):
            if not root:
                return 0
            else:
                left_max_depth = _dfs(root.left)
                right_max_depth = _dfs(root.right)

                return max(left_max_depth, right_max_depth) + 1

        return _dfs(root)

蝦趴簡約遞迴版

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

用 stack 的 DFS 實作

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        stack = [[root, 0]]
        max_depth = 0

        while stack:
            node, depth = stack.pop()
            max_depth = max(max_depth, depth)

            if node:
                stack.append([node.left, depth + 1])
                stack.append([node.right, depth + 1])

        return max_depth

用 queue 的 BFS 實作

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        queue = deque([root])
        level = 0

        while queue:
            for i in range(len(queue)):
                node = queue.popleft()

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            level += 1

        return level

時間複雜度

O(n)，n 是 binary tree 的 node 個數。

空間複雜度

O(h)，h 是 binary tree 的高度。

結語

Tree 的 pattern 要熟記 (繼續對自己喊話)

• About
• Latest Posts

數據女巫 𝔻.𝕡𝕪𝕤 🔮

𝐀𝐈 𝐀𝐫𝐭𝐢𝐬𝐭 • 𝐒𝐨𝐟𝐭𝐰𝐚𝐫𝐞 𝐄𝐧𝐠𝐢𝐧𝐞𝐞𝐫
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art

Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 🔮 (see all)

• [推薦工具] 讓程式碼截圖變的美美的吧！VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
• [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
• [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26