计算二叉树中唯一子树的数量

Question

我最近遇到了这个求二叉树中唯一子树数量的面试题。如何做到这一点？

Answer 1

我猜你的意思是 "Universal value sub trees" - see the description here

在这种情况下，您只需实现树的遍历，如果每个节点的所有子节点都等于父节点，则将其加 1（因为您已经确定了一个通用价值树）

Answer 2

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

计算二叉树中唯一子树的数量

Counting the number of unival subtrees in a binary tree

algorithm

binary-tree