在树的遍历中，有条件地计算节点--递归地计算。

Question

我正在做一个大学作业，要求比较一棵树上的节点，并对满足某个条件的节点进行计数。我可以看到我可以用堆栈遍历树等方式来迭代完成这个任务，但我确信讲师们正在寻找一个递归的解决方案，而我正在为这个特殊的实现而苦恼。

我目前的（有缺陷的）实现是。

public int traverseIncrement(User user, User reference) {

    if(user == null)
        return 0;

    int count = 1;

    if (user.getLeft() != null) {
        if(user.getLevel() > reference.getLevel()) {
            count += traverseIncrement(user.getLeft(), reference);
        }
    }

    if (user.getRight() != null) {
        if(user.getLevel() > reference.getLevel()) {
            count += traverseIncrement(user.getRight(), reference);
        }
    }

    return count;       
}

有两个明显的问题 第一是第一个节点从未被评估过 第二是我总是比所需的输出高一档。如果有任何正确的方向，我将会很有帮助。

Answer 1

我认为这两个问题是相关的。而不是假设 count 是1，然后根据是否满足条件进行递归，你应该将 count 取决于条件，然后递归。换句话说，将给定节点的评估留给处理该节点的调用。

此外，你也可以省去检查左或右是否是 null 因为你的函数已经在输入时检查了。

public int traverseIncrement(User user, User reference) {
    if(user == null)
        return 0;

    int count = (user.GetLevel() > reference.getLevel()) ? 1 : 0;

    count += traverseIncrement(user.getLeft(), reference);
    count += traverseIncrement(user.getRight(), reference);

    return count;
}