題目

給定一個二叉樹，找出其最大深度。

難度：★★☆☆☆
類型：二叉樹

二叉樹的深度為根節(jié)點到最遠葉子節(jié)點的最長路徑上的節(jié)點數(shù)。

說明: 葉子節(jié)點是指沒有子節(jié)點的節(jié)點。

示例

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

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

解答

方案1：遞歸法

遞歸法通過遍歷所有結(jié)點尋找最大深度，時間復雜度為N。我們編寫函數(shù)，確定以root為根結(jié)點的一棵樹的最大深度這樣：

1. 如果根結(jié)點root為空，則直接返回0；

2. 如果不為空，則是左子樹的最大深度d1和右子樹的最大深度d2中較大的值加1。

3. 左子樹或右子樹的最大深度可以通過調(diào)用本函數(shù)確定。

具體這樣實現(xiàn)：

class Solution:
    """
    遞歸法
    """
    def maxDepth(self, root):
        def max_depth(root):                        # 計算以root為根節(jié)點的二叉樹的最大深度
            if not root:
                return 0
            max_left = max_depth(root.left)         # 左子樹最大深度
            max_right = max_depth(root.right)       # 右子樹最大深度
            return max(max_left, max_right) + 1     # 加上根節(jié)點，返回當前子樹最大深度
        return max_depth(root)

方案2：迭代法

我們把每一個結(jié)點及其對應的深度作為一條記錄，使用棧這個數(shù)據(jù)結(jié)構(gòu)來存儲每條記錄，遍歷樹的每一個結(jié)點，并用max_depth變量記錄遍歷到當前位置的最大深度，直到棧中為空為止。

class Solution:
    """
    迭代法
    """
    def maxDepth(self, root):
        stack = []                                              # 定義一個空棧，棧中的元素是結(jié)點及其對應的深度
        if root:                                                # 如果根結(jié)點不為空
            stack.append((root, 1))                             # 則將根節(jié)點及其對應深度1組成的元組入棧
        max_depth = 0                                           # 初始化最大深度為零
        while stack:                                            # 當棧非空時
            tree_node, cur_depth = stack.pop()                  # 彈出棧頂結(jié)點及其對應的深度
            if tree_node:                                       # 如果該結(jié)點不為空
                max_depth = max(max_depth, cur_depth)           # 更新當前最大深度，如果該結(jié)點深度更大的話
                stack.append((tree_node.left, cur_depth+1))     # 將該結(jié)點的左孩子結(jié)點及其對應深度壓入棧中
                stack.append((tree_node.right, cur_depth+1))    # 將該結(jié)點的右孩子結(jié)點及其對應深度壓入棧中
        return max_depth                                        # 返回遍歷結(jié)束后的最大深度

如有疑問或建議，歡迎評論區(qū)留言~