Проверка коэффициента баланса каждого узла в BST и сохранение его в узле

Question

Я пытаюсь написать эту функцию, которая будет хранить баланс каждого узла в BST и сохранять его внутри узла. В моем BST я добавил переменную bal, чтобы сохранить ее.

Я все еще начинающий, когда дело доходит до рекурсии, поэтому извините за любые ошибки, мне просто нужна помощь, чтобы увидеть, правильна ли моя логика или есть ли лучший способ! Вот моя функция:

 void calculateBalanceValue(BinaryNode *& t)
        {
            if (t==nullptr) return;

            int left = height(t->left);
            int right = height(t->right);
            t->bal=abs(left -right);
            calculateBalanceValue(t->right);
            calculateBalanceValue(t->left);

        }

Answer 1

Логика выглядит разумной для меня, но мне кажется, что было бы довольно тривиально сделать ее примерно в два раза быстрее.

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

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

Поскольку мы не хотим изменять указатель, передаваемый в эту функцию, я просто передам указатель по значению.

int calculateBalanceValue(BinaryNode *t)
    {
        if (t==nullptr) 
            return 0;

        int left = calculateBalance(t->left);
        int right = calculateBalance(t->right);
        t->bal=abs(left -right);
        return 1 + std::max(left, right);
    }

Кроме того, если вы хотите критиковать рабочий код, вы можете проверить на веб-сайте Stack Exchange Code Review , который посвящен именно этому.