Java - 將樹轉換爲相同深度的節點列表

我正在嘗試編寫代碼以將二叉樹轉換爲具有相同深度的節點列表。如果樹的深度爲d，則會創建d列表。邏輯是按順序遍歷並將當前遍歷的節點添加到適當深度的列表中。Java - 將樹轉換爲相同深度的節點列表

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);

將這項工作？有沒有我沒有處理的角落案件？此外，現在我傳遞List的列表以便由方法返回，因爲我無法想象在方法中初始化它並在最後返回它的方式，同時還保留遞歸結構。有一個更好的方法嗎？

來源

2016-10-27 Haseeb Javed

完整高度爲4的二叉樹將有8種不同的可能路徑。在這種情況下，列表將如何？ –

你有一般的概念非常完美。它會工作，並應處理所有情況。

然而，你必須在細節上有幾個誤區：

您的時候添加新的名單已在錯誤的方向比較檢查。它應該是if (treeList.size() <= depth)。
每次撥打inOrderWithHeight()（您沒有提供任何代碼）應該是遞歸調用treeToListofNodesByLevel()。保持前兩個參數不變，然後通過treeList作爲第三個參數。
這是一個更多的樣式問題，但參數類型通常應聲明爲滿足您實際需要的最高級別類型。這裏沒有必要指定ArrayList或LinkedList，任何List都可以。將treeList參數的類型更改爲List<List<Node<T>>>。

對於初始化List內的方法同時也使用遞歸的問題，這就是實現幫助器方法的用途。以treeToListofNodesByLevel的當前正文並將其移入私有方法（遞歸調用發生更改，以便私有方法調用它自己），我們將其稱爲treeToListofNodesByLevelHelper。然後改變目前的公共方法如下：

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

來源

2016-10-27 05:07:36 Douglas

我不明白「inOrderWithHeight」在幹什麼。我爲這個問題做了什麼（未優化）是使用兩個隊列像BFS一樣遍歷，並且每次迭代都會將該深度的節點添加到該迭代列表中（每次迭代遍歷樹的一個深度）。這是因爲你在你的答案應該我的代碼做一個二叉樹：

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); 
     }  
    } 
}

我寫了這對飛不通過語法檢查，並可能有編譯器錯誤。但希望你明白這個主意。

來源

2016-10-27 04:46:58 masec

幾乎在那裏......請注意，您只爲'currDepth == 0'的'treeList'添加一個新的'LinkedList'，因此您需要爲其他深度另外添加'add'。 – ajb

謝謝。我編輯了我的答案。 – masec

爲什麼你只需要使用相同的函數的代碼會更加美麗：

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);

來源

2018-01-19 06:18:18

Java - 將樹轉換爲相同深度的節點列表

回答

相關問題