Java - ツリーを同じ深さのノードのリストに変換する

Question

バイナリツリーを同じ深さのノードのリストに変換するコードを記述しようとしています。ツリーに深さdがある場合は、d個のリストが作成されます。このロジックは、順序通りのトラバースを行い、現在トラバースされているノードを適切な深さのリストに追加することです。

public void treeToListofNodesByLevel(Node<T> n,int depth, ArrayList<LinkedList<Node<T>>> treeList){ 

     if(n.right != null){ 
      inOrderWithHeight(n.right, depth + 1); 
     } 
     if(treeList.size() >= depth){ 
      treeList.add(depth, new LinkedList<Node<T>>()); 
     } 
     treeList.get(depth).add(n); 
     if(n.left != null){ 
      inOrderWithHeight(n.left, depth + 1); 
     } 

    } 

、その後の呼び出し：

ArrayList<LinkedList<Node<T>>> result = new ArrayList<LinkedList<Node<T>>>(); 
treeToListofNodesByLevel(root, 0, result); 

ウィルこの仕事を？私が扱っていないコーナーケースはありますか？ また、リストのリストをメソッドから返すようになっています。これは、メソッド内で初期化し、その後にそれを返し、再帰構造を維持する方法を考えることができないためです。これを行うより良い方法はありますか？

Answer 1

あなたは一般的な概念をかなり完全に持っています。それは動作し、すべてのケースを処理する必要があります。

しかし、あなたは細部でいくつかのエラーがあります：

• を新しいリストを追加するときのためにあなたのチェックが間違った方向に比較しています。それはif (treeList.size() <= depth)でなければなりません。
• inOrderWithHeight()（コードは提供していません）への各呼び出しは、treeToListofNodesByLevel()への再帰呼び出しである必要があります。最初の2つの引数はそのままで、3番目の引数にはtreeListを渡します。
• これはスタイルの問題ですが、実際に必要なものを満たす最高レベルのタイプとしてパラメータタイプを宣言する必要があります。 ArrayListまたはLinkedListと指定する必要はありません。Listとなります。 treeListパラメータのタイプをList<List<Node<T>>>に変更します。

再帰をも使用しながらメソッド内でリストを初期化するには、それは実装ヘルパーメソッドのためのものです。 treeToListofNodesByLevelの現在の本文を取得し、それをプライベートメソッドに移動します（プライベートメソッドが自身を呼び出すように再帰呼び出しを変更して）、treeToListofNodesByLevelHelperとしましょう。そして、これに現在の公開方法を変更する：あなたはちょうど同じ機能を使用する理由

public List<List<Node<T>>> treeToListofNodesByLevel(Node<T> node) { 
    List<List<Node<T>>> result = new ArrayList<>(); 
    treeToListofNodesByLevelHelper(node, 0, result); 
    return result; 
} 

Answer 2

"inOrderWithHeight"メソッドが何をしているのか分かりません。私はこの質問（最適化されていない）のために、2つのキューを使ってBFSのように横断し、その繰り返しのリストにその深さのノードを追加します（各反復はツリーの1つの深さを走査しています）。ここでは、あなたの答えになって、バイナリツリーのためにそれを行うには、私のコードは次のとおりです。

Queue<Node<T>> queue1 = new LinkedList<Node<T>>() ; 
Queue<Node<T>> queue2 = new LinkedList<Node<T>>() ; 
public void treeToListofNodesByLevel(Node<T> root, ArrayList<LinkedList<Node<T>>> treeList) { 
    if (root == null) 
     return; 
    int curr_depth = 0; 
    queue1.add(root); 
    while(!queue1.isEmpty()){ 
     treeList.add(curr_depth, new LinkedList<Node<T>>()); 
     while(!queue1.isEmpty()){ 
      Node<T> node = queue1.remove(); 
      treeList.get(curr_depth).add(node); 
      if(node.left != null) queue2.add(node.left); 
      if(node.right != null) queue2.add(node.right); 
     } 
     curr_depth++; 
     while(!queue2.isEmpty()){ 
      Node<T> node = queue2.remove(); 
      queue1.add(node); 
     }  
    } 
} 

私は構文チェックせずにその場でこれを書いて、コンパイルエラーを有することができます。しかし、うまくいけば、あなたはそのアイデアを得ます

Answer 3

コードがより美しいようになります。あなたの主な機能には

public void treeToListofNodesByLevel(BinaryTree node, int currentDepth, List<List<BinaryTree>> result){ 

    // Check if the list for the currentDepth is created 
    if(result.get(currentDepth) != null){ 
     result.add(currentDepth, new ArrayList<BinaryTree>()) 
    } 

    // Add the current node to the list 
    result.get(currentDepth).add(node); 


    // Recursive the left node 
    if(node.left != null){ 
     treeToListofNodesByLevel(node.left, currentDepth+1, result); 
    } 

    // Recursive the right node 
    if(node.right != null){ 
     treeToListofNodesByLevel(node.right, currentDepth+1, result); 
    } 
} 

：

List<List<BinaryTree>> result = new ArrayList<>(); 
BinaryTree root = new BinaryTree(); 
treeToListofNodesByLevel(root, 0, result);