트리에서 주어진 노드 이전의 리프를 계산하는 방법은 무엇입니까?

Question

그 트리의 주어진 요소 앞에있는 리프의 수를 반환하는 함수를 구현하는 방법은 무엇입니까? 당신이 왼쪽에서 오른쪽으로 나무를 읽고 있다고 가정하십니까?

나는 그것을하기 위해 멀리 찾았지만 매우 간단하지 않고 예외 메커니즘을 사용한다. 나는 그것을 할 우아한 방법이있을 것이라고 생각한다.

Answer 1

어쩌면 당신은 단지 나무를 dfs 할 수 있고, 잎을 세고, 모든 노드에 그것을 저장할 수 있습니다. like

int count; 

void dfs(int x){ 
    dfs(x->left); 
    leafBefore[x] = count; 
    if (x is leaf) count += 1; 
    dfs(x->right); 
} 

count = 0; 
dfs(root);