104. Maximum Depth of Binary Tree

Problem

Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

https://leetcode.com/problems/maximum-depth-of-binary-tree/

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 3

Example 2:

Input: root = [1,null,2]
Output: 2

Constraints:

The number of nodes in the tree is in the range [0, 10^4].
-100 <= Node.val <= 100

Test Cases

# 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:

solution_test.py

import pytest

import sys
sys.path.append('..')
from _utils.binary_tree import build_tree
from solution import Solution

null = None


@pytest.mark.parametrize('root, expected', [
    ([3,9,20,null,null,15,7], 3),
    ([1,null,2], 2),
])
class Test:
    def test_solution(self, root, expected):
        sol = Solution()
        assert sol.maxDepth(build_tree(root)) == expected

Thoughts

相当于 102. Binary Tree Level Order Traversal 的简化版，只记录层数，不输出节点的值。

直接用层序（level-order）遍历二叉树，或者其他顺序也行。

Code

solution.py

from collections import deque
from typing import Optional

import sys
sys.path.append('..')
from _utils.binary_tree import TreeNode


# 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:
        queue = deque()
        queue.append((root, 0))
        while len(queue) > 0:
            root, level = queue.popleft()
            if root is not None:
                queue.append((root.left, level + 1))
                queue.append((root.right, level + 1))

        return level

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。