Description:
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.
Examples:
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 3
Example 2:
Input: root = [1,null,2]
Output: 2Solution in Python:
To solve the problem of finding the maximum depth of a binary tree in Python, we can use a recursive approach. The idea is to traverse the tree and compute the depth of each subtree, then use the maximum depth between the left and right subtrees plus one (for the current node) as the result.
Python
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
# If the tree is empty, return 0 (base case)
if root is None:
return 0
# Recursively find the maximum depth of the left subtree
left_depth = self.maxDepth(root.left)
# Recursively find the maximum depth of the right subtree
right_depth = self.maxDepth(root.right)
# The maximum depth of the current node is the maximum of the depths of the
# left and right subtrees plus 1 (for the current node)
return max(left_depth, right_depth) + 1Explanation:
- TreeNode Definition:
- The
TreeNodeclass defines the structure of a binary tree node. Each node has a value (val), a left child (left), and a right child (right).
- The
- Method
maxDepth:- Base Case:
- If
rootisNone(the tree is empty or we have reached the end of a branch), return 0. This base case stops the recursion.
- If
- Recursive Case:
- Compute the maximum depth of the left subtree by calling
self.maxDepth(root.left). This recursive call continues until the base case is reached for the left subtree. - Compute the maximum depth of the right subtree by calling
self.maxDepth(root.right). Similarly, this recursive call continues until the base case is reached for the right subtree.
- Compute the maximum depth of the left subtree by calling
- Combine Results:
- The maximum depth at the current node (
root) is the greater of the maximum depths of the left and right subtrees plus 1 (to account for the current node itself). - Use
max(left_depth, right_depth) + 1to compute the depth at the current node.
- The maximum depth at the current node (
- Return:
- The final result is the maximum depth of the tree, which is returned from the initial call to
maxDepth.
- The final result is the maximum depth of the tree, which is returned from the initial call to
- Base Case:
This approach ensures that every node in the tree is visited once, and the depth is calculated by aggregating the depths of the subtrees. This algorithm has a time complexity of O(N), where N is the number of nodes in the tree, as each node is processed once.
Solution in Javascript:
JavaScript
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function(root) {
// If the tree is empty, return 0 (base case)
if (root === null) {
return 0;
}
// Recursively find the maximum depth of the left subtree
let leftDepth = maxDepth(root.left);
// Recursively find the maximum depth of the right subtree
let rightDepth = maxDepth(root.right);
// The maximum depth of the current node is the maximum of the depths of the
// left and right subtrees plus 1 (for the current node)
return Math.max(leftDepth, rightDepth) + 1;
};Solution in Java:
Java
class Solution {
public int maxDepth(TreeNode root) {
// If the tree is empty, return 0 (base case)
if (root == null) {
return 0;
}
// Recursively find the maximum depth of the left subtree
int leftDepth = maxDepth(root.left);
// Recursively find the maximum depth of the right subtree
int rightDepth = maxDepth(root.right);
// The maximum depth of the current node is the maximum of the depths of the
// left and right subtrees plus 1 (for the current node)
return Math.max(leftDepth, rightDepth) + 1;
}
}Solution in C#:
C#
public class Solution {
public int MaxDepth(TreeNode root) {
// If the tree is empty, return 0 (base case)
if (root == null) {
return 0;
}
// Recursively find the maximum depth of the left subtree
int leftDepth = MaxDepth(root.left);
// Recursively find the maximum depth of the right subtree
int rightDepth = MaxDepth(root.right);
// The maximum depth of the current node is the maximum of the depths of the
// left and right subtrees plus 1 (for the current node)
return Math.Max(leftDepth, rightDepth) + 1;
}
}