題目：

給定一個二叉樹root,返回其最大深度

二叉樹的最大深度是指從根節點到最遠葉子節點的最長路徑上的節點數

---

方法一：深度優先搜索

知道了左子樹和右子樹的最大深度l和r，那么該二叉樹的最大深度即為:max(l,r)+1

而左子樹和右子樹的最大深度又可以以同樣的方式進行計算。因此可以用「深度優先搜索」的方法來計算二叉樹的最大深度。具體而言，在計算當前二叉樹的最大深度時，可以先遞歸計算出其左子樹和右子樹的最大深度，然后在O(1)時間內計算出當前二叉樹的最大深度。遞歸在訪問到空節點時退出。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def maxDepth(self, root):""":type root: Optional[TreeNode]:rtype: int"""if root is None:return 0else:left_height=self.maxDepth(root.left)right_height=self.maxDepth(root.right)return max(left_height,right_height)+1

時間復雜度：O(n)n為二叉樹節點的個數。每個節點在遞歸中只被遍歷一次。

空間復雜度：O(height)其中height表示二叉樹的高度

---

方法二：廣度優先搜索

廣度優先搜索的隊列里存放的是「當前層的所有節點」。每次拓展下一層的時候，用一個變量ans來維護拓展的次數，該二叉樹的最大深度即為ans。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def maxDepth(self, root):""":type root: Optional[TreeNode]:rtype: int"""if not root:return 0queue=[root] #使用一個隊列（queue）來進行廣度優先搜索, 初始時包含根節點 ans=0while queue: #在隊列不為空時持續進行。每次循環表示遍歷樹的一層size=len(queue)  #獲取當前隊列中節點的數量，即當前層的節點數while size>0:node=queue.pop(0)if node.left:queue.append(node.left) #當前節點 node 有左子節點，就將左子節點加入隊列if node.right:queue.append(node.right)#當前節點 node 有右子節點，就將右子節點加入隊列size-=1  #處理完當前節點，減少層內節點計數ans+=1 #層處理完，增加深度計數器return ans

時間復雜度：O(n)每個節點只會被訪問一次

空間復雜度：O(n)取決于隊列存儲的元素數量

源自力扣官方題解