day14 二叉树的最大深度

要计算二叉树的最大深度，可以采用递归的方法。递归的基本思想是：二叉树的最大深度等于其左子树和右子树的最大深度加1。以下是详细的步骤和代码实现：

方法思路

递归终止条件：如果当前节点为空（即 node == NULL），则返回深度0。
递归计算左右子树的深度：分别计算左子树和右子树的最大深度。
返回当前节点的深度：当前节点的深度为左右子树深度的较大值加1。

解决代码#include <algorithm> // 用于 std::maxstruct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};int maxDepth(TreeNode* root) { if (root == nullptr) { return 0; } int left_depth = maxDepth(root->left); int right_depth = maxDepth(root->right); return std::max(left_depth, right_depth) + 1;}代码解释

结构体定义：TreeNode 结构体定义了二叉树的节点，包含一个整数值 val 和两个指向左右子节点的指针。
递归函数 maxDepth：
终止条件：如果当前节点 root 为空，返回0。
递归计算左右子树深度：分别递归调用 maxDepth 计算左子树和右子树的深度。
返回结果：返回左右子树深度的较大值加1，表示当前子树的深度。

这种方法通过递归遍历每个节点，确保每个子树的深度都被正确计算，最终得到整个二叉树的最大深度。时间复杂度为 O(n)，其中 n 是二叉树的节点数，因为每个节点仅被访问一次。空间复杂度为 O(h)，其中 h 是二叉树的高度，这是由于递归调用栈的深度最多为树的高度。

您可能感兴趣问答

Collapsible

热门标签

热点问答