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 更新的是路径长度（左深度 + 右深度）。