java - 计算二叉树中具有特定值的节点

Question

我试图想出一种方法来递归地遍历二叉树而不是迭代地遍历二叉树，并计算找到特定值的次数。我遇到的一个问题是第一种方法中的 root。

节点内部类:

private class Node {

    int data;
    Node root;
    Node left;
    Node right;
}

递归和辅助方法:

public int valCount(int val) {
    if (root != null) {
        return valCount(val, root);
    }
    return 0;
}

public int valCount(int val, Node root) {
    int cnt = 0;
    if (root.left != null) {
        if (root.left.data == val) {
            cnt++;
        }
        valCount(val, root.left);
    }


    if (root.right != null) {
        if (root.right.data == val) {
            cnt++;
        }
        valCount(val, root.right);
    }
    return cnt;
}

由于根本问题，我无法进行测试，因此我不完全确定我的输出是否正确。所以，这个问题需要问...我是否走在正确的轨道上？我的方法有意义吗？任何帮助都是极好的。干杯!

Answer 1

每次调用 valCount 时，都会创建局部变量 cnt 的单独副本。因此，当您为根调用 valCount 时，会创建一个变量 cnt；当 valCount 然后为左子树或右子树调用自身时，新的 valCount 拥有其自己的 cnt，因此当它们递增 cnt，但不递增第一个 valCount 拥有的 cnt。这意味着 valCount 为左子树和右子树所做的所有工作都将被丢弃。

解决此问题的一个简单方法是注意，当您为左子树或右子树调用 valCount 时，递归调用将返回一个值。您应该使用该值，而不是丢弃结果:

int leftCount = valCount(val, root.left);

然后用 leftCount 做一些事情(我会让你思考如何使用它)。

编辑:还有一件事:valCount应该查看root.data，但它不应该查看root。 left.data 或 root.right.data。让递归调用完成查看子树中数据的工作。这就是二叉树递归通常的工作原理。