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, 104].
-100 <= Node.val <= 100
Solutions
Solution 1: Recursion
Recursively traverse the left and right subtrees, calculate the maximum depth of the left and right subtrees, and then take the maximum value plus $1$.
The time complexity is $O(n)$, where $n$ is the number of nodes in the binary tree. Each node is traversed only once in the recursion.
1 2 3 4 5 6 7 8 9101112
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defmaxDepth(self,root:TreeNode)->int:ifrootisNone:return0l,r=self.maxDepth(root.left),self.maxDepth(root.right)return1+max(l,r)
1 2 3 4 5 6 7 8 910111213141516171819202122232425
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */classSolution{publicintmaxDepth(TreeNoderoot){if(root==null){return0;}intl=maxDepth(root.left);intr=maxDepth(root.right);return1+Math.max(l,r);}}
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcmaxDepth(root*TreeNode)int{ifroot==nil{return0}l,r:=maxDepth(root.Left),maxDepth(root.Right)return1+max(l,r)}