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

Optimal Approach

Simple post order recursion, calculate the height of the left and right subtrees and return 1 + their maximum height.

Time: O(n)

Space: O(1), Recursive stack space: O(n)