问题描述:给的那个一个二叉树struct Node{int val;Node*left;Node*right;Node*next;}填充他的每个next种子很,让这个指针主席昂其下一个右侧几点。如果找不到下一个右侧节点(同一层中的右侧节点),则将next指针设置为null。初始状态下,所有next指针都被设置为NULL。
BFS求解:对于这种同一层的这种问题,使用BFS求解具有较好的效果。
public Node fillRight(Node root)
{
Queue<Node>queue=new LinkedList<>();
queue.add(root);
while(!queue.isEmpty())
{
int queueSize=queue.size();
Node theLastNode=queue.poll();
if(theLastNode.left!=null){queue.add(theLastNode.left);}
if(theLastNode.right!=null){queue.add(theLastNode.right);}
for(int i=1;i<queueSize;i++)
{
Node theNextNode=queue.poll();
if(theNextNode.left!=null){queue.add(theNextNode.left);}
if(theNextNode.right!=null){queue.add(theNextNode.right);}
theLastNode.next=theNextNode;
theLastNode=theNextNode;
}
theLastNode.next=null;
}
???????return root;
}