(java实现,层次遍历)填充每个节点的下一个右侧节点指针
程序员文章站
2022-05-20 20:09:02
...
给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。
初始状态下,所有 next 指针都被设置为 NULL。
思路:使用层次遍历依次将每层节点存入队列,每次节点出队列node.next=queue.peek();
这个地方存在一个问题,每次一层节点出队列,下一层的节点需要进队列,此时需要判断出队列的节点是否是该层的最后一个节点,如果是则node.next=null;
class Solution {
Queue<Node> queue=new LinkedList<Node>();
public Node connect(Node root) {
if(root==null){
return root;
}
if(root.left==null&&root.right==null){
return root;
}
queue.add(root);
while(!queue.isEmpty()){
int size=queue.size();
//for循环保证单层节点的出队列
for(int i=0;i<size;i++){
Node node=queue.poll();
//判断是不是该层的最后一个节点
if(i==size-1){
node.next=null;
}else{
node.next=queue.peek();
}
if(node.left!=null){
queue.add(node.left);
queue.add(node.right);
}
}
}
return root;
}
}
上一篇: 一个走迷宫题
推荐阅读
-
填充每个节点的下一个右侧节点指针 II
-
117. 填充每个节点的下一个右侧节点指针 II
-
【C语言 LeetCode 116】填充每个节点的下一个右侧节点指针
-
leetcode116. 填充每个节点的下一个右侧节点指针
-
leetcode117. 填充每个节点的下一个右侧节点指针 II
-
leetcode116. 填充每个节点的下一个右侧节点指针/层次遍历
-
leetcode116. 填充每个节点的下一个右侧节点指针
-
【leetcode】117. 填充每个节点的下一个右侧节点指针 II(populating-next-right-pointers-in-each-node-ii)(bfs)[中等]
-
leetcode116. 填充每个节点的下一个右侧节点指针
-
leetcode117. 填充每个节点的下一个右侧节点指针 II