algorithm - 填充树的所有节点的数据字段

Question

A node of a binary tree has two pointers, 'left' and 'right', and two data fields, 'leftcount' and 'rightcount'. 'leftcount' specifies the number of nodes in the left subtree of the node, and 'rightcount' specifies the number of nodes in the right subtree of the node. Write an algorithm to populate the data fields of all the nodes of the tree.

我在一次采访中被问到这个问题。我想出了一个基于树的后序遍历的解决方案。有人可以指导我吗？

Answer 1

这应该有效(我相信):

int populateCounters(Node* node) {
    if(node == NULL) return 0;
    node->leftCount = populateCounters(node->left);
    node->rightCount = populateCounters(node->right);
    return node->leftCount + node->rightCount + 1;
}