c++ - 二叉树递归方法的直径

Question

我正在尝试使用递归查找直径，我对递归感到困惑

我试过的一些测试用例我在某些时候得到了正确的答案 发生整数溢出，但以下作者的解决方案被接受了相同的数据类型

我的方法:

对于每个节点，经过它的最长路径的长度=它的左子树的最大深度+它的右子树的最大深度。

我的问题是我的实现有什么问题

  class Solution {
  public:
      int mx = 0;
      int solve(TreeNode* root) {
          if (root == NULL)return 0;
          int leftheight = diameterOfBinaryTree(root->left) + 1;
          int rightheight = diameterOfBinaryTree(root->right) + 1;
          mx = max(mx, leftheight + rightheight);
          return max(leftheight, rightheight);
      }
      int diameterOfBinaryTree(TreeNode* root) {
          solve(root);
          return mx;
      }

  };

作者的方法:相同的方法但不同的递归实现

  class Solution {
  public:
      int maxdiadepth = 0;

      int dfs(TreeNode* root) {
          if (root == NULL) return 0;

          int leftdepth = dfs(root->left);
          int rightdepth = dfs(root->right);

          if (leftdepth + rightdepth > maxdiadepth) maxdiadepth = leftdepth + rightdepth;
          return max(leftdepth + 1, rightdepth + 1);
      }

      int diameterOfBinaryTree(TreeNode* root) {
          dfs(root);

          return maxdiadepth;
      }
  };

Answer 1

在工作实现中，递归 dfs 调用返回子树的最大深度。

在您的实现中，递归 diameterOfBinaryTree 调用返回当前累积的直径近似值。您将它分配给名为 leftheight 和 rightheight 的变量 - 这是误导；该值实际上不是左子树或右子树的高度。