GoCalf Calf 的自留地 · 昙花一现

104. Maximum Depth of Binary Tree

Calf

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:

case1
case1

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

Example 2:

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

Constraints:

Constraints:

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

Test Cases

python 
# 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下载完整源码
py 
import pytest

import os
import sys
sys.path.append(os.path.dirname(os.path.dirname(__file__)))
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下载完整源码
py 
from collections import deque
from typing import Optional


# 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

评论需要 JavaScript。