如何求出python二叉樹的深度

題目描述

輸入一棵二叉樹的根節(jié)點(diǎn)，求該樹的深度。從根節(jié)點(diǎn)到葉節(jié)點(diǎn)依次經(jīng)過的節(jié)點(diǎn)（含根、葉節(jié)點(diǎn)）形成樹的一條路徑，最長路徑的長度為樹的深度。

• 節(jié)點(diǎn)總數(shù) <= 10000

題目樣例

示例

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

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

題目思考

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

解決方案

方案 1

思路

• 先考慮遞歸做法, 嘗試 DFS
• 我們可以這樣構(gòu)造遞歸方法: 傳入節(jié)點(diǎn), 返回當(dāng)前節(jié)點(diǎn)的深度, 該深度是左右子樹的最大深度+1
• 假設(shè)葉子節(jié)點(diǎn)的深度為 1, 顯然根節(jié)點(diǎn)的深度就是整個(gè)樹的最大深度了
• 遞歸出口即節(jié)點(diǎn)為空的情況, 此時(shí)深度為 0

復(fù)雜度

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

代碼

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

方案 2

思路

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

復(fù)雜度

• 時(shí)間復(fù)雜度 O(N): 需要遍歷整個(gè)樹
• 空間復(fù)雜度 O(N): 隊(duì)列的空間消耗

代碼

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