LeetCode #104 二叉樹的最大深度
題目描述
給定一個二叉樹,找出其最大深度。
二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。
說明: 葉子節點是指沒有子節點的節點。
示例:
給定二叉樹 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
傳回它的最大深度 3 。
方法一:DFS 遞歸
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if root is None:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1;
- 時間複雜度: O ( N ) O(N) O(N)
- 空間複雜度: O ( N ) O(N) O(N)
方法二:DFS 疊代
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def maxDepth(self, root: TreeNode) -> int:
stack = []
if root is not None:
stack.append((1, root))
depth = 0
while stack:
# 取出最後一個
current_depth, root = stack.pop()
if root is not None:
depth = max(depth, current_depth)
stack.append((current_depth + 1, root.left))
stack.append((current_depth + 1, root.right))
return depth
- 時間複雜度: O ( N ) O(N) O(N)
- 空間複雜度: O ( N ) O(N) O(N)
方法三:BFS 疊代
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def maxDepth(self, root: TreeNode) -> int:
# BFS
if root is None:
return 0
queue = [(1, root)]
while queue:
# 取出第一個
depth, node = queue.pop(0)
if node.left:
queue.append((depth+1,node.left))
if node.right:
queue.append((depth+1,node.right))
return depth
- 時間複雜度: O ( N ) O(N) O(N)
- 空間複雜度: O ( N ) O(N) O(N)