LeetCode 力扣热题100 二叉树的直径

class Solution {
public:// 定义一个变量 `maxd`，用于存储当前二叉树的最大直径。int maxd = 0; // 主函数，计算二叉树的直径。int diameterOfBinaryTree(TreeNode* root) {// 调用 `maxDepth` 函数进行递归计算，并更新 `maxd`。maxDepth(root);// 返回计算得到的最大直径。return maxd;}// 定义 `maxDepth` 函数，计算二叉树的深度，同时更新直径。public:int maxDepth(TreeNode* root) {// 如果当前节点为空，则返回深度为 0。if (root == nullptr) {return 0;}// 递归计算左子树的深度。int l_depth = maxDepth(root->left);// 递归计算右子树的深度。int r_depth = maxDepth(root->right);// 更新最大直径：通过当前节点的左右子树深度之和来计算路径长度。maxd = max(l_depth + r_depth, maxd);// 返回当前节点的最大深度（左右子树深度的最大值 + 当前节点）。return max(l_depth, r_depth) + 1;}
};

假设我们有一个二叉树如下：

        1

       / \

      2   3

     / \     

    4   5  

运行过程：

1. 初始化阶段：

• maxd = 0

• 调用 diameterOfBinaryTree(root)，其中 root 指向节点 1。

2. 递归展开 maxDepth(root)：

• 以节点 1 为根，计算左子树和右子树的深度。

左子树递归（以 2 为根）：

• 调用 maxDepth(root->left)，进入节点 2。

左子树的左子树递归（以 4 为根）：

• 调用 maxDepth(root->left->left)，进入节点 4。

• 节点 4 的左右子树为空：

• 调用 maxDepth(root->left->left->left) 返回 0。

• 调用 maxDepth(root->left->left->right) 返回 0。

• 通过节点 4 的路径长度为 0 + 0 = 0。

• maxd = max(0, maxd) = 0。

• 返回节点 4 的深度：max(0, 0) + 1 = 1。

左子树的右子树递归（以 5 为根）：

• 调用 maxDepth(root->left->right)，进入节点 5。

• 节点 5 的左右子树为空：

• 调用 maxDepth(root->left->right->left) 返回 0。

• 调用 maxDepth(root->left->right->right) 返回 0。

• 通过节点 5 的路径长度为 0 + 0 = 0。

• maxd = max(0, maxd) = 0。

• 返回节点 5 的深度：max(0, 0) + 1 = 1。

回到节点 2：

• 左子树深度为 1（节点 4）。

• 右子树深度为 1（节点 5）。

• 通过节点 2 的路径长度为 1 + 1 = 2。

• maxd = max(2, maxd) = 2。

• 返回节点 2 的深度：max(1, 1) + 1 = 2。

右子树递归（以 3 为根）：

• 调用 maxDepth(root->right)，进入节点 3。

• 节点 3 的左右子树为空：

• 调用 maxDepth(root->right->left) 返回 0。

• 调用 maxDepth(root->right->right) 返回 0。

• 通过节点 3 的路径长度为 0 + 0 = 0。

• maxd = max(0, maxd) = 2。

• 返回节点 3 的深度：max(0, 0) + 1 = 1。

回到节点 1：

• 左子树深度为 2（节点 2）。

• 右子树深度为 1（节点 3）。

• 通过节点 1 的路径长度为 2 + 1 = 3。

• maxd = max(3, maxd) = 3。

• 返回节点 1 的深度：max(2, 1) + 1 = 3。

结果：

• 最终，maxd = 3，表示二叉树的最大直径为 3。

• 返回值为 3。

递归总结：

• 每次递归调用时，我们计算左右子树的深度，并利用它们更新全局变量 maxd。

• maxDepth 返回的是当前节点的深度，而 maxd 更新的是路径长度（左深度 + 右深度）。