在二叉樹中計算具有特定值的節點

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局部變量。