0%
Loading ...

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

image 1723702035748

題目解釋

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

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

範例

file

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

root 到最遠且同層的 157 的節點數量都是 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 要熟記 (繼續對自己喊話)

數據女巫 𝔻.𝕡𝕪𝕤 🔮

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

The reCAPTCHA verification period has expired. Please reload the page.