计算二叉树中出现的次数

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