深入理解多叉树最大深度算法（递归）

GeekLiHua

发布于 2025-01-21 15:52:17

1570

文章被收录于专栏：JavaJava

深入理解多叉树最大深度算法（递归）

多叉树的最大深度问题是树结构中的一个基础算法题目，通过递归的思想能够清晰地解决。本文将深入讨论多叉树最大深度的算法，并提供相应的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。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-01-12，如有侵权请联系 cloudcommunity@tencent.com 删除

递归