Вычислить высоту дерева на каждом узле, помогите мне объяснить это решение кода

Question

Вот фрагмент кода решения, которое вычисляет высоту каждого узла в двоичном дереве и сохраняет высоту в каждом узле. Код рекурсивно просматривает дерево, а ниже - конструктор Node.

class Node {
public:
  int height; // to be set by computeHeight()
  Node *left, *right;
  Node() { height = -1; left = right = nullptr; }
  ~Node() {
    delete left;
    left = nullptr;
    delete right;
    right = nullptr;
  }
};

Ниже представлена ​​функция, которая вычисляет и сохраняет высоту для каждого Node. Я не понимаю, как leftHeight и rightHeight обновляются с помощью n->left->height и n->right->height, если при строительстве height установлено на -1?

void computeHeight(Node *n) {

if (n == nullptr) {
    return;
}

computeHeight(n->left);
computeHeight(n->right);

int leftHeight = -1;
int rightHeight = -1;

if (n->left != nullptr) {
    leftHeight = n->left->height;
}

if (n->right != nullptr) {
    rightHeight = n->right->height;
}

n->height = std::max(leftHeight, rightHeight) + 1;

}

Вот главный файл, который запускает функцию computeHeight

int main() {
  Node *n = new Node();
  n->left = new Node();
  n->right = new Node();
  n->right->left = new Node();
  n->right->right = new Node();
  n->right->right->right = new Node();
  n->right->right->right->left = new Node();

  computeHeight(n);

  delete n;
  n = nullptr;

  return 0;

}

Answer 1

Представьте себе листовой узел (левый и правый - nullptr). Тогда n->left != nullptr и n->right != nullptr ложны, поэтому вычисление фактически становится

int leftHeight = -1;
int rightHeight = -1;
n->height = std::max(leftHeight, rightHeight) + 1;

, что эффективно

n->height = 0;

Теперь из-за способа выполнения рекурсии каждый узел получает это рост рассчитывается после это дети рассчитывают свой рост. Итак, представьте узел с двумя дочерними узлами, каждый из которых является листовым узлом. Мы уже видели, что листовые узлы имеют нулевую высоту. Таким образом, вычисление для такого узла эффективно

int leftHeight = -1;
int rightHeight = -1;
if (n->left != nullptr) {
    leftHeight = 0; // because n->left is a leaf node
}
if (n->right != nullptr) {
    rightHeight = 0; // because n->right is a leaf node
}
n->height = std::max(leftHeight, rightHeight) + 1;

, что означает, что вы получите n->height = 1 для этого узла.

И так далее. Эти вычисления производятся вверх по дереву, начиная с листьев, пока, наконец, root не установит свою высоту.

Answer 2

Мы можем решить эту проблему с помощью базового c случая индукции. По сути, давайте начнем с базового случая, а затем, предполагая, что любой вариант n работает, мы должны проверить, работает ли случай n+1. В случае вычисления высот узлов в двоичном дереве базовый случай - это когда узел root является листовым узлом, а для случая n+1 узлы левой / правой стороны - это варианты n. Вы можете думать об этом так, как n - это высота текущего узла, а n=0 - это базовый случай листового узла.

Когда узел root является листом, левый и правый узлы являются nullptr метод по существу превращается в

void computeHeight(Node *n) {
    int leftHeight = -1;
    int rightHeight = -1;

    n->height = std::max(leftHeight, rightHeight) + 1;
}

, и в этом случае n->height становится 0, что правильно для листового узла. Теперь, когда узел не является листовым, операторы

computeHeight(n->left);
computeHeight(n->right);

уже вызываются перед вычислением. По сути, это делает так, что мы предполагаем, что и левый, и правый узлы уже позаботились, и их высота правильная. Затем мы можем использовать высоту левого и правого узлов для вычисления высоты root узла, которая вычисляется через

int leftHeight = -1;
int rightHeight = -1;

if (n->left != nullptr) {
    leftHeight = n->left->height;
}

if (n->right != nullptr) {
    rightHeight = n->right->height;
}

n->height = std::max(leftHeight, rightHeight) + 1;

Хитрость здесь в том, что мы уже вызвали computeHeight() слева и правые боковые узлы, так что, когда мы делаем вычисления на текущем узле, мы можем с уверенностью предположить, что дочерние узлы полностью позаботились. Кроме того, дочерние узлы вычисляются перед узлом root, поэтому программа сначала просочится вниз к листьям, а затем вернется вверх и вычислит нелистовые узлы.