algorithm - 如何计算树中给定节点之前的叶子？

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