2

二分探索木の高さ/深さを見つけるための反復的な方法を試していました。基本的に、幅優先検索を使用して深さを計算し、キューを使用してツリー ノードを格納し、整数のみを使用してツリーの現在の深さを保持しようとしました。ツリー内の各ノードはキューに入れられ、子ノードがないかチェックされます。子ノードが存在する場合、深さ変数がインクリメントされます。コードは次のとおりです。

public void calcDepthIterative() {
    Queue<TreeNode> nodeQ = new LinkedList<TreeNode>();
    TreeNode node = root;
    int level = 0;
    boolean flag = false;

    nodeQ.add(node);
    while(!nodeQ.isEmpty()) {
        node = nodeQ.remove();
        flag = false;
        if(node.leftChild != null) {
            nodeQ.add(node.leftChild);
            flag = true;
        }

        if(node.rightChild != null) {
            nodeQ.add(node.rightChild);
            flag = true;
        }
        if(flag) level++;
    }
    System.out.println(level);

}

ただし、コードはすべてのケースで機能するわけではありません。たとえば、次のツリーの場合:

     10
   /    \
  4      18
   \    /  \
    5  17   19

深度が 2 ではなく 3 として表示されます。このページのアイデアを使用して、追加のキューを使用して現在の深度を保存する代替バージョンを作成しました。追加のキューの使用を避けたかったので、最適化を試みました。追加の Queue を使用しても機能するコードを次に示します。

public void calcDepthIterativeQueue() {
    Queue<TreeNode> nodeQ = new LinkedList<TreeNode>();
    Queue<Integer> lenQ = new LinkedList<Integer>();

    TreeNode node = root;
    nodeQ.add(node);
    lenQ.add(0);
    int maxLen = 0;
    while(!nodeQ.isEmpty()) {
        TreeNode curr = nodeQ.remove();
        int currLen = lenQ.remove();
        if(curr.leftChild != null) {
            nodeQ.add(curr.leftChild);
            lenQ.add(currLen + 1);
        }

        if(curr.rightChild != null) {
            nodeQ.add(curr.rightChild);
            lenQ.add(currLen + 1);
        }
        maxLen = currLen > maxLen ? currLen : maxLen;
    }
    System.out.println(maxLen);

}

質問：

正しい深さを返すように最初のメソッドを修正する方法はありますか?

編集 以下の受け入れられた回答を参照

riciの答えのJavaコード：

public void calcDepthIterative() {
    Queue<TreeNode> nodeQ = new LinkedList<TreeNode>();
    int depth = 0;
    nodeQ.add(root);
    while(!nodeQ.isEmpty()) {
        int nodeCount = nodeQ.size();
        if(nodeCount == 0)
            break;
        depth++;
        while(nodeCount > 0) {
            TreeNode topNode = nodeQ.remove();
            if(topNode.leftChild != null)
                nodeQ.add(topNode.leftChild);
            if(topNode.rightChild != null)
                nodeQ.add(topNode.rightChild);
            nodeCount--;
        }
    }
    System.out.println(depth);
}
4

3 に答える 3

6

これを行う1つの方法は次のとおりです。

Create a Queue, and push the root onto it.
Let Depth = 0
Loop:
    Let NodeCount = size(Queue)
    If NodeCount is 0:
        return Depth.
    Increment Depth.
    While NodeCount > 0:
        Remove the node at the front of the queue.
        Push its children, if any, on the back of the queue
        Decrement NodeCount.

使い方

が設定されるたびNodeCountに、スキャンは新しい行を開始しようとしています。NodeCount は、その行のノード数に設定されます。これらのノードがすべて削除されると (つまり、NodeCount がゼロに減分されると)、行が完了し、その行のノードのすべての子がキューに追加されるため、キューは再び完全な行を持ちます。 NodeCount は、その行のノードの数に再び設定されます。

于 2013-02-22T02:13:16.493 に答える
1 
public int height(Node root){
  int ht =0;
  if(root==null) return ht;
  Queue<Node> q = new ArrayDeque<Node>();
  q.addLast(root);
  while(true){
      int nodeCount = q.size();
      if(nodeCount==0) return ht;
      ht++;
      while(nodeCount>0){
       Node node = q.pop();
       if(node.left!=null) q.addLast(node.left);
       if(node.right!=null) q.addLast(node.right);
       nodeCount--;
      }
 }
于 2014-04-15T09:02:36.947 に答える
-3

再発はどうですか、

int Depth(Node node)
{
    int depthR=0,depthL=0;
    if(Right!=null)depthR=Depth(Right);
    if(Left!=null)depthL=Depth(Left);
    return Max(depthR,depthL)+1;
}

touがゼロベースの深さを必要とする場合は、結果の深さを1だけ減算します。

于 2013-02-22T05:29:37.973 に答える