сбалансированное дерево - улучшение

Question

я иметь следующую структуру для представления двоичного дерева:

typedef struct node *pnode; 
typedef struct node { 
    int val; 
    pnode left; 
    pnode right; 
} snode; 

Веса дерева является суммой параметра val из всех узлов дерева. Мы говорим, что дерево сильно сбалансировано, когда оно пустое или вес слева равен весу правого поддерева, и каждое поддерево (слева и справа) сильно сбалансировано. Я должен написать функцию, которая говорит, является ли дерево или не сильно сбалансировано.

Код я написал:

int getWeight(pnode tree) 
{ 
    if(! tree) 
     return 0; 
    return getWeight(tree->left) + getWeight(tree->right) 
      + tree->val; 
} 

bool isStronglyBalanced(pnode tree) 
{ 
    if(! tree) 
     return true; 

    int wL, wR; 
    wL = getWeight(tree->left); 
    wR = getWeight(tree->right); 

    if(wL != wR) 
     return false; 
    return (isStronglyBalanced(tree->left) && isStronglyBalanced(tree->right)); 
} 

Функция выше делает свою работу очень хорошо, но я заметил это посещение узлы дерева более чем один раз. Может ли быть улучшено (возможно, с помощью динамического программирования), чтобы посещать каждый из узлов дерева только один раз?

Answer 1

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

Существует несколько подходов к возврату двух частей информации из вызова функции. Если бы было какое-то возвращаемое значение, которое, как вы знали, никогда не было бы весом поддерева (возможно, отрицательным числом), вы могли бы использовать это как сигнал, что поддерево не было сильно сбалансированным. Или вы можете просто вернуть два значения: a bool и int. (В C вы должны использовать аргумент «out» для одного из них.) Или вы можете определить составной объект с двумя значениями, который в C будет struct { bool balanced; int weight; }.

Однако вы это делаете, логика такая же. В следующем псевдокоде, я предполагаю, что вы можете вернуть пары значений, как вы можете в некоторых языках (C++, например, но, несмотря на любое случайное сходство, это все еще псевдокод):

pair<bool, int> get_weight(tree) { 
    if (!tree) return {true, 0}; 
    balanced, weight_left = get_weight(tree->left); 
    if (!balanced) return {false, 0};  /* Returned weight doesn't matter */ 
    balanced, weight_right = get_weight(tree->right); 
    return {balanced && weight_left == weight_right, 
      2 * weight_right + tree->val}; /* weight_left == weight_right */ 
}