回答のアプローチは Recursive DFS BFS Iterative DFS

Base case root が empty children が Null

Recursive DFS

Time complexity: O(n) Mem complexity: O(n)

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

BFS

BFS を使う場合は Queue を使う。

  3

／　 ＼ 9 20 ／＼ 15 7

| 3 | 9 | 20 | 15 | 7 |

1 2 2 3 3 ← Level

| 3 |

1

Queue を deque していくと 最終的に Queue の値がなくなるので、 その時に level を返す。

if not root:
    retunr 0

level = 0
q = deque([root])
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

Iterative DFS

Pre-order DFS

stack

| node depth |

| 3 1 |

pop して

| node depth |

| 20 2 |

| 9 2 |

pop して

| node depth |

| 20 2 |

20 には子がいるので、stack に追加

| node depth |

| 7 3 |

| 15 3 |

stack = [[root, 1]]
res = 0

while stack:
    node, depth = stack.pop()

    if node:
        res = max(res, depth)
        stack.append([node.left, depth + 1])
        stack.append([node.right, depth + 1])
return res