[LeetCode Road] Maximum Depth of Binary Tree - Solution/C++

104. Maximum Depth of Binary Tree

Question:

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:

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

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

Input: root = []
Output: 0

Input: root = [0]
Output: 1

Constraints:

The number of nodes in the tree is in the range [0, 10^4].

-100 <= Node.val <= 100

Source code

Version 1

Idea:
Basically, I konw the search must be throughout all link of the whole tree, then if the left/right node of root are NULL, the depth is the deepest, so depth is start from 1 (depth + 1). But, I can't find out any regular action by using the recursion.

There is a quit clear demonstration as below[1]: It's very helpful and let me understand the recursion processing. So, let me explain the code:
(1) maxDepth(root->left): use recursion to find deepest depth of left node
(2) maxDepth(root->right: use recursion to find deepest depth of right node
(3) max((1), (2)): compare the deepest depth of both of left/right nodes, get the maximum value. Then, + 1 means adding this layer.

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

Reference:
[1] https://algorithms.tutorialhorizon.com/find-the-maximum-depth-or-height-of-a-binary-tree/