二叉树的直径

题面

给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

示例 1：

输入： root = [1,2,3,4,5] 输出： 3 解释： 3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

示例 2：

输入： root = [1,2] 输出： 1

提示：

• 树中节点数目在范围 [1, 104] 内
• -100 <= Node.val <= 100

分析

• 一棵树中的节点之间的最长路径，就是其左右子树的最大深度之和

  /**
   * Definition for a binary tree node.
   * struct TreeNode {
   *     int val;
   *     TreeNode *left;
   *     TreeNode *right;
   *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
   *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
   *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
   * right(right) {}
   * };
   */
  class Solution {
  public:
      int maxWidth = 0;
      int maxDepth(TreeNode* root) {
          if (root == nullptr) { // 递归结束条件，返回其深度为 0
              return 0;
          }
          int l_depth =
              maxDepth(root->left); // 分发给左子树，请你计算你的深度是多少
          int r_depth =
              maxDepth(root->right); // 分发给右子树，请你计算你的深度是多少
          maxWidth = max(maxWidth, l_depth + r_depth);
          return max(l_depth, r_depth) +
                 1; // 最终汇总，最大深度就是左右子树的最大深度+1
      }
      int diameterOfBinaryTree(TreeNode* root) {
          maxDepth(root);
          return maxWidth;
      }
  };

• 自顶向下的逻辑

  /**
   * Definition for a binary tree node.
   * struct TreeNode {
   *     int val;
   *     TreeNode *left;
   *     TreeNode *right;
   *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
   *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
   *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
   * right(right) {}
   * };
   */
  class Solution {
  public:
      int diameterOfBinaryTree(TreeNode* root) {
          // 定义局部变量存储最大直径，替代原成员变量
          int maxWidth = 0;
          
          // 定义内部递归函数，通过引用更新maxWidth
          function<int(TreeNode*)> dfs = [&](TreeNode* node) -> int {
              if (node == nullptr) {
                  return 0;
              }
              // 递归计算左右子树深度
              int l_depth = dfs(node->left);
              int r_depth = dfs(node->right);
              
              // 更新最大直径（当前节点左右子树深度之和）
              maxWidth = max(maxWidth, l_depth + r_depth);
              
              // 返回当前节点的最大深度
              return max(l_depth, r_depth) + 1;
          };
          
          // 执行递归，触发maxWidth的更新
          dfs(root);
          
          // 返回最终的最大直径
          return maxWidth;
      }
  };