트리의 모든 노드의 데이터 필드 채우기

Question

이진 트리의 노드에는 '왼쪽'과 '오른쪽'이라는 두 개의 포인터와 'leftcount'와 'rightcount'라는 두 개의 데이터 필드가 있습니다. 'leftcount'는 노드의 왼쪽 하위 트리에있는 노드 수를 지정하고 'rightcount'는 노드의 오른쪽 하위 트리에있는 노드 수를 지정합니다. 트리의 모든 노드의 데이터 필드를 채우는 알고리즘을 작성하십시오.

나는 인터뷰에서이 질문을 받았다. 트리의 포스트 오더 트래버 설 (postorder traversal)을 기반으로 한 솔루션을 생각해 냈습니다. 누군가 나를 안내 해줄 수 있습니까?

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