104. Maximum Depth of Binary Tree

Question: Maximum Depth of Binary Tree

Solution1. recursive DFS

💡 recursive 的寫法： 1. 終止條件 2. 呼叫自己

1. 如果 node 沒有東西，就不是一層: if node == None: return 0 （終止條件）
2. 如果 node 有東西，就至少是一層: if root ≠ None: return 1 + ….
3. + 後面要接，小孩層數中較大的那一層。目的是要找所在層的最大層數，所以要看左/右 children，並取大的: max(dfs(node.left), dfs(node.right))

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

class Solution:

def maxDepth(self, root: Optional[TreeNode]) -> int:

if root == None:

return 0

return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

Solution2. BFS

1. need a queue (先進先出): q = deque([root])
2. 一次檢查完同一層的 node: for i in range(len(q))，此時 level = 0
1. 先加進來的 node，先檢查: q.popleft()
2. 如果有 children，就往後 append 到 deque 裡面
3. 這一層的 node 都檢查完後 level += 1 

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

class Solution:

def maxDepth(self, root: Optional[TreeNode]) -> int:

if root == None:

return 0

q = deque([root])

level = 0

while q:

for i in range(len(q)):

node = q.popleft()

if node.left:

q.append(node.left)

if node.right:

q.append(node.right)

level += 1

return level

Solution3. iteratively DFS

1. need a stack: nodes = list()
2. 從第一層的 root 開始檢查，每次都存 node 與他的層數: nodes = [[root, 1]]
3. 如果 nodes 裡有東西，就檢查: while nodes
1. 把最後一個 node 拿出來: pop()
2. 如果 node 存在
3. 看他是第幾層，與現有最大層數比較，記起來: res = max(res, depth)
4. 檢查 node 的 left & right children，如果 children 存在，則繼續往後append，並把深度 +1 (depth + 1) 
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
nodes = [[root, 1]]
res = 0
while nodes:
node, depth = nodes.pop()
if node:
res = max(res, depth)
nodes.append([node.left, depth + 1])
nodes.append([node.right, depth + 1])
return res

Video Solution