BST - 左と右の子を持つノードのカウント

Question

タイトルに記載されているとおり、私は左と右の両方の子を持つBSTのノードを数えるだけでこの問題を解決しようとしています。私はこれを解決するための論理を考えるのに苦労しています。

私はこのようなことを考えました。

まず、ルートがnullかどうか、またはnullの子があるかどうかを確認します。次に、右に向かうツリーをたどって、子供をチェックし続け、条件が満たされたらカウンタを増分します。しかし、私が最終ノードに到達して、左の子が横断するノードに戻る必要がある場合はどうなりますか？私は一番前の親を追跡する一時ノードを持っていましたが、複数のレベルを上がる必要があるのはどうですか？私はこの問題に対する答えは再帰的に解決することを前提としていますが、どこから始めるべきか分かりません。ここで

は、私が持っているものです。

public int fullNodes() { 
    int count = 0; 
    Node n = root; 
    Node temp = null; 

    if (n == null || n.left == null && n.right == null) return count; 

    count++; //increment count, since the root has children on both sides 

    temp = n; //hold the previous place 
    n = n.right; //go right 

    //Now what? 

    return count; 
} 

私はまだ問題解決には、私の質問に加えて、どのように再帰的に考えることを学ぶないとき再帰的に考えるのに苦労していますか？ちょっとした練習、または問題を解決するために使うテクニックやヒントがありますか？

Answer 1

以前のノードを保持するために一時変数を使用するのではなく、1の深さでしか動作しません。子ノードで同じ関数を呼び出します。

再帰ツリートラバーサルは次のようになります：

public int countSomething (Node node) { 

    // Self; 
    // 
    int result = 1; // use your required logic here 

    // Children; 
    //  
    if (node.left != null) 
     result += countSomething(node.left); 
    if (node.right != null) 
     result += countSomething(node.right); 

    // done. 
    return result; 
} 


// example usages 
int treeTotal = countSomething(rootNode); 
int subtreeTotal = countSomething(subtree); 

実行コールスタックは、関数の再帰的呼び出し、その適切なコンテキストでそれぞれ開催します。トップレベルの呼び出しが返されると、呼び出されたツリー全体またはサブツリーに対する答えが合計されます。

ごBSTのための適切なロジックを置く代わりに、一定1.

Answer 2

の最初は、私たちが書く私たちは、その後、あなたのNodeクラスの表現

class Node { 
    public Node left; 
    public Node right; 
    public Node(){} 
    public Node(Node left, Node right) { 
     this.left = left; 
     this.right = right; 
    } 
} 

を作成してみましょう、の「ノードが&右子ども左の両方を持っています」私たちのrecusrive関数とあなたの関数を使っているクライアント