Practice/Google/Leetcode 104. Maximum Depth of Binary Tree

Leetcode 104. Maximum Depth of Binary Tree

CodingOptional

Problem

You are given the root node of a binary tree. Your task is to calculate and return the height (or depth) of this tree.

The height of a binary tree is defined as the number of nodes encountered along the longest path starting from the root and ending at any leaf node. A leaf node is one that has no children.

If the tree is empty (the root is null), the height should be 0.

Requirements

1. Traverse the binary tree to find the longest path from root to leaf
2. Count the total number of nodes along this longest path
3. Handle the case where the tree is empty
4. Return an integer representing the tree height

Constraints

• The number of nodes in the tree is in the range [0, 10000]
• Node values are between -100 and 100
• Your solution should run in O(n) time where n is the number of nodes
• Space complexity should be O(h) where h is the height, due to recursion stack

Examples

Example 1:

Input: root = [3, 9, 20, null, null, 15, 7] Tree structure: 3 / \ 9 20 / \ 15 7 Output: 3 Explanation: The longest path is either 3→20→15 or 3→20→7, both containing 3 nodes.

Example 2:

Input: root = [1, 2, null, 3, null, 4] Tree structure: 1 / 2 / 3 \ 4 Output: 4 Explanation: The path 1→2→3→4 contains 4 nodes.

Example 3:

Input: root = [] Output: 0 Explanation: An empty tree has height 0.

Example 4:

Input: root = [1] Output: 1 Explanation: A single node has height 1.