二叉树的最大深度
题目要求
编写一个函数，该函数接收一个二叉树的根节点 root 作为参数。你需要计算并返回这棵二叉树的最大深度。
二叉树的最大深度定义为从根节点到最远叶子节点的最长路径上的节点数量。
解题思路
要解决这个问题，我们可以采用递归的方法。递归是一种通过函数自己调用自己来重复解决问题的方法。对于二叉树的最大深度问题，我们可以这样考虑：
-
基本情况：如果二叉树为空，即
root为null，那么其最大深度为 0。 -
递归步骤：如果二叉树不为空，我们需要分别计算左子树和右子树的最大深度。这可以通过递归地调用我们的函数来完成。
-
合并结果：一旦我们得到了左子树和右子树的最大深度，二叉树的最大深度就是左右子树深度的最大值加 1（加的 1 是因为我们需要加上根节点本身）。
具体步骤如下：
- 对于每个节点，我们都递归地求其左右子节点的最大深度。
- 对于每个非空节点，其最大深度是其左右子节点的最大深度的较大者加 1。
- 对于空节点，返回深度 0。
- 递归直到所有的叶子节点，叶子节点的最大深度为 1。
- 最后，返回根节点的最大深度，这就是整棵树的最大深度。
通过这种方式，我们可以自底向上地计算出每个节点的最大深度，最终得到整棵树的最大深度。
Golang 版本
package main
import (
"fmt"
)
// TreeNode is a struct for a binary tree node.
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// maxDepth takes a TreeNode and returns the max depth of the tree.
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
leftDepth := maxDepth(root.Left)
rightDepth := maxDepth(root.Right)
if leftDepth > rightDepth {
return leftDepth + 1
}
return rightDepth + 1
}
func main() {
// Example usage:
// Construct a binary tree as an example.
// 3
// / \
// 9 20
// / \
// 15 7
root := &TreeNode{3, &TreeNode{9, nil, nil}, &TreeNode{20, &TreeNode{15, nil, nil}, &TreeNode{7, nil, nil}}}
fmt.Println("Max depth of the tree:", maxDepth(root))
}
这段代码定义了一个二叉树节点的结构体TreeNode，并实现了一个maxDepth函数来计算二叉树的最大深度。main函数中给出了一个示例二叉树，并调用maxDepth函数来输出其最大深度。
C++版本
#include <iostream>
#include <algorithm>
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == NULL) {
return 0;
} else {
int left_depth = maxDepth(root->left);
int right_depth = maxDepth(root->right);
return std::max(left_depth, right_depth) + 1;
}
}
};
int main() {
// Example usage:
TreeNode *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);
Solution solution;
std::cout << "Max depth of the tree: " << solution.maxDepth(root) << std::endl;
// Clean up allocated nodes if necessary
delete root->right->right;
delete root->right->left;
delete root->right;
delete root->left;
delete root;
return 0;
}
这段代码定义了一个二叉树节点的结构体TreeNode，并实现了一个Solution类，其中包含了一个maxDepth成员函数来计算二叉树的最大深度。main函数中创建了一个示例二叉树，并调用maxDepth函数来输出其最大深度。最后，代码中还包含了适当的内存清理操作。
Python 版本
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
else:
left_depth = self.maxDepth(root.left)
right_depth = self.maxDepth(root.right)
return max(left_depth, right_depth) + 1
# Example usage:
if __name__ == "__main__":
# Construct a binary tree as an example.
# 3
# / \
# 9 20
# / \
# 15 7
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
solution = Solution()
print("Max depth of the tree:", solution.maxDepth(root))
这段代码定义了一个二叉树节点的类TreeNode，以及一个解决方案类Solution，其中包含了一个maxDepth方法来计算二叉树的最大深度。在if __name__ == "__main__":块中，我们创建了一个示例二叉树，并调用maxDepth方法来输出其最大深度。
Java 版本
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
} else {
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
}
}
public class Main {
public static void main(String[] args) {
// Example usage:
TreeNode 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);
Solution solution = new Solution();
System.out.println("Max depth of the tree: " + solution.maxDepth(root));
}
}
这段代码定义了一个二叉树节点的类TreeNode，以及一个解决方案类Solution，其中包含了一个maxDepth方法来计算二叉树的最大深度。在Main类的main方法中，我们创建了一个示例二叉树，并调用maxDepth方法来输出其最大深度。
Rust 版本
// Definition for a binary tree node. #[derive(Debug, PartialEq, Eq)] pub struct TreeNode { pub val: i32, pub left: Option<Rc<RefCell<TreeNode>>>, pub right: Option<Rc<RefCell<TreeNode>>>, } impl TreeNode { #[inline] pub fn new(val: i32) -> Self { TreeNode { val, left: None, right: None, } } } use std::rc::Rc; use std::cell::RefCell; use std::cmp::max; impl Solution { pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 { match root { Some(node) => { let left_depth = Solution::max_depth(node.borrow().left.clone()); let right_depth = Solution::max_depth(node.borrow().right.clone()); max(left_depth, right_depth) + 1 }, None => 0, } } } pub struct Solution; fn main() { // Example usage: let root = Some(Rc::new(RefCell::new(TreeNode::new(3)))); let left = Some(Rc::new(RefCell::new(TreeNode::new(9)))); let right = Some(Rc::new(RefCell::new(TreeNode::new(20)))); let left_leaf = Some(Rc::new(RefCell::new(TreeNode::new(15)))); let right_leaf = Some(Rc::new(RefCell::new(TreeNode::new(7)))); if let Some(ref root_node) = root { root_node.borrow_mut().left = left; root_node.borrow_mut().right = right; if let Some(ref right_node) = root_node.borrow().right { right_node.borrow_mut().left = left_leaf; right_node.borrow_mut().right = right_leaf; } } println!("Max depth of the tree: {}", Solution::max_depth(root)); }
这段代码首先定义了一个二叉树节点的结构体TreeNode，以及一个解决方案结构体Solution，其中包含了一个max_depth静态方法来计算二叉树的最大深度。在main函数中，我们创建了一个示例二叉树，并调用max_depth方法来输出其最大深度。在 Rust 中，我们通常使用Rc<RefCell<T>>来共享和修改可变数据，这在树结构中尤其常见。
总结
上面给出了使用不同编程语言（包括 Golang、C++、Python、Java 和 Rust）实现计算二叉树最大深度的解法。这些解法都采用了递归的方式来解决问题。递归的基本思路是对于每个节点，分别计算其左右子节点的最大深度，然后取两者中的较大值加 1 作为当前节点的最大深度。如果节点为空，则返回深度 0。这种递归的方式能够自底向上地计算出每个节点的最大深度，最终得到整棵树的最大深度。虽然使用了不同的编程语言，但基本的解题思路是一致的，这展示了递归在解决二叉树问题时的普适性。