диаметр двоичного дерева рекурсивный подход - PullRequest
Новая
       6

диаметр двоичного дерева рекурсивный подход

1 голос
/ 04 июля 2019

Я пытаюсь найти диаметр с помощью рекурсии, я путаюсь с рекурсией

В некоторых тестовых случаях, которые я пробовал, в какой-то момент я получил правильный ответ Произошло целочисленное переполнение, но ниже авторское решение было принято с теми же типами данных

Мой подход:

Для каждого узла длина самого длинного пути, который его проходит = MaxDepth его левого поддерева + MaxDepth его правого поддерева.

У меня вопрос, что не так с моей реализацией 

  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;
      }
  };

Ответы [ 2 ]

0 голосов
/ 04 июля 2019

В рабочей реализации рекурсивный вызов dfs возвращает максимальную глубину поддерева.

В вашей реализации рекурсивный вызов diameterOfBinaryTree возвращает текущее накопленное приближение к диаметру.Вы назначаете его переменным с именами leftheight и rightheight - это вводит в заблуждение;на самом деле значение не является высотой левого или правого поддерева.

0 голосов
/ 04 июля 2019

Рассмотрим случай, когда вы нажмете на листовой узел, или случай, когда у вас есть только один узел. Ваш алгоритм возвращает 2, что неверно. Эта проблема возникает потому, что вы вычисляете высоту, добавляя единицу к левому / правому поддереву, несмотря ни на что.

Чтобы исправить это, добавьте единицу при возврате высоты, например: max(leftheight, rightheight) + 1

Кстати, когда вы рекурсивно вызываете, вы должны сделать solve(root->left) или solve(root->right), а не diameterOfBinaryTree(root->left): P

...