Подсчет количества подтипов unival в двоичном дереве

Question

Недавно я наткнулся на этот вопрос о поиске количества подтипов unival в двоичном дереве. Как это может быть сделано?

Answer 1

int countUniVals(node* head, bool* unival) { 
    if (!node) { 
     *unival = true; 
     return 0; 
    } 
    bool uniL,uniR; 
    int sum = countUniVals(head->l, &uniL) + countUniVals(head->r, &uniR); 
    if (uniL && uniR && 
     (!head->l || head->l->val == head->val) && 
     (!head->r || head->r->val == head->val)) { 
     sum++; 
     *unival = true; 
    } 
    return sum; 
} 

Answer 2

Я полагаю, вы имеете в виду «Юниверсал значение суб деревья» - see the description here

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