Leetcode 104. Maximum Depth of Binary Tree
Problem Explanation
The problem asks to find the maximum depth of a binary tree. The maximum depth is defined as the number of nodes along the longest path from the root node down to the farthest leaf node. A leaf node is defined as a node with no children.
For instance, given the binary tree:
1 2plaintext 3 3 4 / \ 5 9 20 6 / \ 7 15 7
The maximum depth is 3, because the longest path is from root node 3 to leaf node 7, which contains 3 nodes.
To solve this problem, we will use a Depth-First Search (DFS) recursive approach. Starting from the root, we will traverse each branch of the tree. For each node, we add 1 to the maximum depth of its left or right branch (whichever is greater), and then return the result to the higher level. The base case is when a node is null
, in which case the depth is 0.
Python Solution
1 2python 3class TreeNode: 4 def __init__(self, x): 5 self.val = x 6 self.left = None 7 self.right = None 8 9class Solution: 10 def maxDepth(self, root: TreeNode) -> int: 11 # Base case: if root is null, return 0 12 if not root: 13 return 0 14 15 # Recursive case: return 1 + maximum between left and right depths 16 return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
Java Solution
1
2java
3class TreeNode {
4 int val;
5 TreeNode left;
6 TreeNode right;
7 TreeNode(int x) { val = x; }
8 }
9
10class Solution {
11 public int maxDepth(TreeNode root) {
12 // Base case: if root is null, return 0
13 if (root == null) {
14 return 0;
15 } else {
16 // Recursive case: return 1 + maximum between left and right depths
17 return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
18 }
19 }
20}
JavaScript Solution
1
2javascript
3function TreeNode(val, left, right) {
4 this.val = (val===undefined ? 0 : val)
5 this.left = (left===undefined ? null : left)
6 this.right = (right===undefined ? null : right)
7}
8
9var maxDepth = function(root) {
10 // Base case: if root is null, return 0
11 if (root === null) {
12 return 0;
13 } else {
14 // Recursive case: return 1 + maximum between left and right depths
15 return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
16 }
17};
C++ Solution
1
2cpp
3struct TreeNode {
4 int val;
5 TreeNode *left;
6 TreeNode *right;
7};
8
9class Solution {
10public:
11 int maxDepth(TreeNode* root) {
12 // Base case: if root is null, return 0
13 if (root == nullptr)
14 return 0;
15
16 // Recursive case: return 1 + maximum between left and right depths
17 return 1 + max(maxDepth(root->left), maxDepth(root->right));
18 }
19};
C# Solution
1
2csharp
3public class TreeNode {
4 public int val;
5 public TreeNode left;
6 public TreeNode right;
7}
8
9public class Solution {
10 public int MaxDepth(TreeNode root) {
11 // Base case: if root is null, return 0
12 if (root == null) {
13 return 0;
14 } else {
15 // Recursive case: return 1 + maximum between left and right depths
16 return 1 + Math.Max(MaxDepth(root.left), MaxDepth(root.right));
17 }
18 }
19}
In all the solutions above, we recursively calculate the depth of the left and right branches of a node, then take the maximum between the two and add 1 to represent the current node. We continue doing this until we reach the leaf nodes, which have a depth of 0 since they do not have any children. This way, we can efficiently calculate the maximum depth of a binary tree.## Ruby Solution
1 2ruby 3class TreeNode 4 attr_accessor :val, :left, :right 5 def initialize(val, left = nil, right = nil) 6 @val = val 7 @left = left 8 @right = right 9 end 10end 11 12def max_depth(root) 13 # Base case: if root is null, return 0 14 return 0 unless root 15 16 # Recursive case: return 1 + maximum between left and right depths 17 1 + [max_depth(root.left), max_depth(root.right)].max 18end
Similar to the Python, JS, Java, C++, and C# solutions, the Ruby solution uses a recursive approach to calculate the maximum depth of a binary tree. The base case returns 0 when a null node is encountered (indicative of having reached a leaf node). The recursive case selects the maximum depth between the left and right subtrees and adds 1 for the current node to this maximum value to calculate the ongoing depth.
Closure Note
In conclusion, the key point to solve this problem is understanding how to use recursion to traverse a binary tree. Once you comprehend the depth-first search (DFS) recursion mechanism, you can easily adapt it to calculate various properties of a binary tree, such as its maximum depth, minimum depth, number of nodes, etc. This problem is a good example of how recursion can simplify problems dealing with tree-like data structures.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.