How to solve Leetcode 104. Maximum Depth of Binary Tree

Problem statement

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.

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.

Solution

You have the following recursive relationship between the root and its children.

maxDepth(root) = max(maxDepth(root->left), maxDepth(root->right))

Code

#include <iostream>
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

int maxDepth(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    return 1 + std::max(maxDepth(root->left), maxDepth(root->right));
}

int main() {
    TreeNode fifteen(15);
    TreeNode seven(7);
    TreeNode twenty(20, &fifteen, &seven);
    TreeNode nine(9);
    TreeNode three(3, &nine, &twenty);
    std::cout << maxDepth(&three) << std::endl;
    TreeNode two(2);
    TreeNode one(1, nullptr, &two);
    std::cout << maxDepth(&one) << std::endl;
}

Output:
3
2

Complexity

Runtime: O(N), where N is the number of nodes.
Extra space: O(N).

References

Get my FREE book "10 Classic Coding Challenges"

How to solve Leetcode 104. Maximum Depth of Binary Tree

Comments

More from this blog

Leetcode 59. How To Go Around A Square Matrix In Spiral Order

Leetcode 120. How To Find The Minimum Path From Top To Bottom Of A Triangle

How To Find The Longest Substring Without Repeating Characters

How To Find The Maximal Subarray Having Distinct Elements

Common Mistakes in Coding Interviews and How to Avoid Them

Problem statement

Example 1

Example 2

Constraints

Solution

Code

Complexity

References

Command Palette

Comments

More from this blog

Problem statement

Example 1

Example 2

Constraints

Solution

Code

Complexity

References