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

Question

我想要想出一种方式来迭代遍历二叉树并计算找到特定值的次数。我遇到的一个问题是第一种方法的根源。

节点内部类：

private class Node { 

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

递归& helper方法：

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，他们不增量cnt第一valCount拥有。这意味着valCount为左右子树所做的所有工作都被抛弃了。

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

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

，然后做一些leftCount（我会让你思考如何使用它）。

编辑：一两件事：valCount应该看看root.data，但它不应该看root.left.data或root.right.data。让递归调用完成查看子树中数据的工作。这就是二叉树递归经常发挥作用的原因。

Answer 2

你不需要在你的Node类中有“root”。 “根”是“这个”对象/指针，对吧？将另一个参数“int [] cnt”传递给valCount。将cnt实例化为int [1]。然后在valCount do cnt [0] ++中。在递归结束后的调用函数中，输出cnt [0]。并删除cnt局部变量。