Posted on 2013-04-26 11:23
小明 阅读(2112)
评论(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;
}
}
}