计算二叉树中出现的次数

Question

假设一棵二叉树可以有多个具有相同键的节点。计算其键等于值 v 的节点数。（它不是二叉搜索树）。int countVal(int v)：返回节点数 n where n.key = v结构：public class Tree {    Node root;    public Tree(Node root)         this.root = root;    }    public static class Node {        int key;        Node left;        Node right;        public Node(int key, Node left, Node right) {            this.key = key;            this.left = left;            this.right = right;        }    }}当然解决方法是使用递归，但我找不到正确的方法。

Answer 1

这是问题的解决方案：

public int countVal(int v) {

    if(root == null)

        return -1;

    else

        return countValRec(v, root);

}

private int countValRec(int v, Node node) {

    if(node == null)

        return 0;

    else if(node.key == v)

        return nodeCountValRec(v, node.left) + 1 + nodeCountValRec(v, node.right);

    else

        return nodeCountValRec(v, node.left) + nodeCountValRec(v, node.right);

}