1 題目描述


計算Binary Tree的最大深度。

2 解法

我們先將大問題變成小問題

  1. 大問題：知道一個樹的最大深度
  2. 小問題：讓我們相信遞歸並假設我們已經透過遞歸給出了根的左子樹和右子樹的最大深度。
  3. 大小問題的關係：因此，為了找到這個二元樹的最大深度，我們必須取出遞歸給我們的 2 個深度中的最大值，然後加 1 以將當前級別（即根的級別）考慮到我們的深度中。
  4. 最小的問題是，當 root 是 None 時，我們的深度為 0。

大小問題關係式：max(左子樹深度, 右子樹深度) + 1(root)

寫成python大概會長這樣

1
2
3
4
def maxDepth(self, root: Optional[TreeNode]) -> int:
    if root is None:
        return 0
    return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

還有另一種思維，那就是最小的問題就是當 root 有值，但是就一個節點，沒有 right 與 left，這時候我們的深度就是 1。

1
2
3
4
def maxDepth(self, root: Optional[TreeNode]) -> int:
    if root.right is None and root.left is None:
        return 1
    return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

3 總結

還不是很適應遞迴的思維，所以這個我還是直接偷看了一下解答，不看沒發現，一看不得了，幸好有先學Recursion的思維，不然這題真的會卡住。可以參考一下我的LeetCode 課前預習 - 掌握 Recursion 的思維指南。思考的時候我們想三個方向

  1. 他們的大問題跟小問題分別可以是什麼
  2. 大小問題的關聯式子怎麼寫
  3. 最小問題又是什麼