当前位置： 面试刷题>> 二叉树的最大深度(经典算法150题)
### 题目描述
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
**说明**: 叶子节点是指没有子节点的节点。
### 示例
给定二叉树 `[3,9,20,null,null,15,7]`，
```
3
/ \
9 20
/ \
15 7
```
其最大深度为 3。
### 解题思路
要解决这个问题，我们可以使用递归的方法。递归的基本思想是：对于每个节点，它的最大深度等于其子节点中的最大深度加1（当前节点本身也算一层）。如果节点为空，则深度为0。
### PHP 示例代码
```php
val = $val;
$this->left = $left;
$this->right = $right;
}
}
function maxDepth($root) {
if ($root === null) {
return 0;
}
$leftDepth = maxDepth($root->left);
$rightDepth = maxDepth($root->right);
return max($leftDepth, $rightDepth) + 1;
}
// 示例用法
$root = new TreeNode(3);
$root->left = new TreeNode(9);
$root->right = new TreeNode(20);
$root->right->left = new TreeNode(15);
$root->right->right = new TreeNode(7);
echo maxDepth($root); // 输出: 3
?>
```
### Python 示例代码
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def maxDepth(root):
if not root:
return 0
left_depth = maxDepth(root.left)
right_depth = maxDepth(root.right)
return max(left_depth, right_depth) + 1
# 示例用法
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(maxDepth(root)) # 输出: 3
```
### JavaScript 示例代码
```javascript
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
function maxDepth(root) {
if (!root) {
return 0;
}
const leftDepth = maxDepth(root.left);
const rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
// 示例用法
const root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);
console.log(maxDepth(root)); // 输出: 3
```
这些代码示例都展示了如何递归地计算二叉树的最大深度。在面试中，能够清晰地阐述递归思想和实现细节是非常重要的。