如何統計樹中給定節點之前的葉子？

Question

你將如何實現一個函數，該函數返回樹中給定元素之前找到的葉子數量？假設你從左到右閱讀樹？

我發現了做它，但它不是很直接，並使用異常機制，我認爲可能有一個優雅的方式來做到這一點？

Answer 1

也許你可以只是dfs樹，計算葉子，將它保存到每個節點。像

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