Posted on 2013-04-26 11:23
小明 閱讀(2132)
評論(0) 編輯 收藏 所屬分類:
數據結構和算法
分析：
題目不難，但是在面試時，在有限的時間內，沒有bug寫出，還是很考驗功力的。
解決這個問題的思路是逐層掃描，上一層設置好下一層的next關系，在處理空指針的時候要格外小心。
代碼如下，有注釋，應該很容易看懂：
使用了三個指針：
node:當前節點
firstChild:下一層的第一個非空子節點
lastChild:下一層的最后一個待處理（未設置next)的子節點
public void connect(TreeLinkNode root) {
TreeLinkNode node = root;
TreeLinkNode firstChild = null;
TreeLinkNode lastChild = null;
while(node!=null){
if(firstChild == null){ //記錄第一個非空子節點
firstChild = node.left!=null?node.left:node.right;
}
//設置子節點的next關系，3種情況
if(node.left!=null && node.right!=null){
if(lastChild!=null){
lastChild.next = node.left;
}
node.left.next = node.right;
lastChild = node.right;
}
else if(node.left!=null){
if(lastChild!=null){
lastChild.next = node.left;
}
lastChild = node.left;
}
else if(node.right!=null){
if(lastChild!=null){
lastChild.next = node.right;
}
lastChild = node.right;
}
//設置下一個節點，如果本層已經遍歷完畢，移到下一層的第一個子節點
if(node.next!=null){
node = node.next;
}
else{
node = firstChild;
firstChild = null;
lastChild = null;
}
}
}