問題：https : //www.education.io/m/connect-all-siblings
我試圖通過創建一個虛擬節點來連接所有同級節點，并使用 next 指標將其設定為我們當前正在訪問的節點的旁邊，但在執行代碼后：
public static void populate_sibling_pointers(BinaryTreeNode root) {
if(root == null) return;
Queue<BinaryTreeNode> q = new LinkedList<>();
q.offer(root);
while(!q.isEmpty()){
int size = q.size();
BinaryTreeNode dummy = new BinaryTreeNode(0);
for(int i = 0; i < size; i ){
BinaryTreeNode cur = q.poll();
dummy.next = cur;
dummy = dummy.next;
if(cur.left!=null){
q.offer(cur.left);
}
if(cur.right!=null){
q.offer(cur.right);
}
}
}
}
我仍然沒有通過一些測驗，但我不確定我在這里做錯了什么。任何幫助表示贊賞！
uj5u.com熱心網友回復：
兩個問題：
您應該創建一個
new虛擬節點僅一次。通過在回圈的每次迭代中創建一個新的while回圈，您可以打破next參考鏈。因此，該節點的創建應該發生之前的while回圈。next鏈中的最后一個節點應next設定為null。
這是更正后的代碼：
class connectSiblings{
public static void populate_sibling_pointers(BinaryTreeNode root) {
if(root == null) return;
Queue<BinaryTreeNode> q = new LinkedList<>();
q.offer(root);
BinaryTreeNode dummy = new BinaryTreeNode(0);
while(!q.isEmpty()){
int size = q.size();
for(int i = 0; i < size; i ){
BinaryTreeNode cur = q.poll();
dummy.next = cur;
dummy = dummy.next;
if(cur.left!=null){
q.offer(cur.left);
}
if(cur.right!=null){
q.offer(cur.right);
}
}
}
dummy.next = null;
}
}
您可以通過將使用替換為LinkedList您正在使用next參考構建的實際鏈表來進一步優化此代碼：當樹的一個層已正確連接到next參考時，您可以迭代該鏈表的該部分以查找并連接下一層的節點，然后可以作為下一層的鏈表，等等。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/315003.html