題目描述

輸入一棵二叉樹的根節點，求該樹的深度。從根節點到葉節點依次經過的節點（含根、葉節點）形成樹的一條路徑，最長路徑的長度為樹的深度。

• 節點總數 <= 10000

題目樣例

示例

給定二叉樹 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。

題目思考

1. 如果限制只能用遞歸或者迭代, 如何解決?

解決方案

方案 1

思路

• 先考慮遞歸做法, 嘗試 DFS
• 我們可以這樣構造遞歸方法: 傳入節點, 返回當前節點的深度, 該深度是左右子樹的最大深度+1
• 假設葉子節點的深度為 1, 顯然根節點的深度就是整個樹的最大深度了
• 遞歸出口即節點為空的情況, 此時深度為 0

復雜度

• 時間復雜度 O(N): 需要遍歷整個樹
• 空間復雜度 O(H): H 表示樹的高度, 也即遞歸的棧的消耗

代碼

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            # 遞歸出口, 空節點的情況
            return 0
        # 當前節點深度是左右子樹的最大深度+1
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
        # 也可以進一步簡化為只需要一行代碼..
        # return 0 if not root else 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

方案 2

思路

• 如果要求必須用迭代方式實現, 那方案 1 就不行了
• 迭代一般可以先嘗試 BFS, 這道題也不例外
• 通過分析題目, 顯然這里的深度就是指 BFS 的層數, 所以完全可以利用                       劍指 Offer 32 - II. 從上到下打印二叉樹 II - leetcode 劍指 offer 系列的做法得出層數, 只是不需要打印出每一層的節點, 只需要統計層數即可. 不清楚的同學可以先看看那道題的思路~
• 下面代碼對必要的步驟有詳細的解釋, 方便大家理解

復雜度

• 時間復雜度 O(N): 需要遍歷整個樹
• 空間復雜度 O(N): 隊列的空間消耗

代碼

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        q = [root]
        res = 0
        while q:
            # 當前層節點數目
            curlen = len(q)
            for node in q[:curlen]:
                # 只追加非空子節點
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            # 隊列切片, 開始處理下一層
            q = q[curlen:]
            # 當前層遍歷完畢, 深度+1
            res += 1
        return res