深入理解多叉树最大深度算法（递归）
多叉树的最大深度问题是树结构中的一个基础算法题目，通过递归的思想能够清晰地解决。本文将深入讨论多叉树最大深度的算法，并提供相应的C++代码。
了解多叉树
多叉树是树结构的一种扩展，每个节点可以有多个子节点。在解决多叉树相关问题时，计算树的最大深度是一项重要任务。多叉树的节点结构通过数组存储其子节点，每个节点可以动态地拥有不同数量的子节点。
示例多叉树：
A / | \ B C D / \ | \ E F G H
使用递归解决最大深度问题
递归是解决多叉树问题的常见方法。通过递归，我们可以轻松地定义问题的基本情况（递归出口）和递归步骤。在计算多叉树的最大深度时，我们可以递归地计算每个子节点的深度，并选择最大的深度作为当前节点的深度。
以下是基于递归的C++代码：
#include <iostream> #include <vector> using namespace std; // 定义多叉树节点 struct TreeNode { char val; vector<TreeNode*> children; TreeNode(char c) : val(c) {} }; class Solution { public: int maxDepth(TreeNode* root) { if (!root) return 0; // 空节点的深度为0 int maxChildDepth = 0; for (TreeNode* child : root->children) { int childDepth = maxDepth(child); maxChildDepth = max(maxChildDepth, childDepth); } return maxChildDepth + 1; // 当前节点深度为其子节点最大深度 + 1 } }; int main() { // 构建示例多叉树 TreeNode* root = new TreeNode('A'); root->children.push_back(new TreeNode('B')); root->children.push_back(new TreeNode('C')); root->children.push_back(new TreeNode('D')); root->children[0]->children.push_back(new TreeNode('E')); root->children[0]->children.push_back(new TreeNode('F')); root->children[2]->children.push_back(new TreeNode('G')); root->children[2]->children.push_back(new TreeNode('H')); // 计算最大深度 Solution solution; int maxDepth = solution.maxDepth(root); cout << "The maximum depth of the tree is: " << maxDepth << endl; return 0; }
在这个递归算法中，我们对每个子节点递归调用 maxDepth 函数，计算其深度，并选择最大深度。通过递归的方式，我们能够清晰地表达树的层级关系，最终得到树的最大深度。在上述示例中，最大深度为3。
如果大家觉得有用的话，可以关注我下面的微信公众号，极客李华，我会在里面更新更多行业资讯，企业面试内容，编程资源，如何写出可以让大厂面试官眼前一亮的简历，让大家更好学习编程，我的抖音，B站也叫极客李华。
