c++ - 如何计算给定数字出现在二叉树中的次数？

Question

有人可以让我知道为什么我的代码不起作用吗？我试图使用递归计算给定值出现在二叉树中的次数。但是，这种方法不起作用。我非常感谢您的反馈和见解。谢谢。

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

public int valCount(int val, Node *root) {
  int cnt = 0;
  if (root->left != null) {
    if (root->data == val) {
        cnt++;
    }
    int leftValCount = valCount(val, root->left);
  }
  if (root->right != null) {
    if (root->data == val) {
        cnt++;
    }
    int rightValCount = valCount(val, root->right);
  }
  return cnt + leftValCount + rightValCount;
}

Answer 1

递归中的一个常见错误是担心当前框架以外的堆栈框架。让递归为您完成这项工作。遵循此经验法则使代码更容易推理。

该算法很简单:对于每个节点，如果当前节点与目标值匹配，则返回1，否则返回0，并在左右子树上添加调用同一函数的结果。基本情况是使用空根调用该函数时，返回0。

int valCount(int val, Node *root) {
    if (!root) return 0;

    return (root->val == val ? 1 : 0) + 
           valCount(val, root->left) + 
           valCount(val, root->right);
}