给我们一棵普通树【非完全二叉树,也就是说:如果一个根结点的右子树不为null,并不能代表 它大的左子树 不为null】,这不是填充每个节点的下一个右侧节点指针I.
让我们将其使用孩子兄弟法来表示。
/*
// Definition for a Node.
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;
}
};
*/
class Solution {
public Node connect(Node root) {
if(root == null){
return root;
}
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
for(int i= 0;i < size;i++){
Node tmp = queue.poll();
if(i < size - 1){
tmp.next = queue.peek();
}
if(tmp.left != null){
queue.offer(tmp.left);
}
if(tmp.right != null){
queue.offer(tmp.right);
}
}
}
return root;
}
}
下面是这种做法的关键。
class Solution {
public Node connect(Node root) {
if(root == null){
return root;
}
// 将cur 当 一个链表
Node cur = root;
while(cur!=null){
// 在遍历当层的时候,将下一层的节点连接起来。
// 为了方便操作,使用了一傀儡节点
Node dummy = new Node();
// 每一层的起始节点 的 前一个节点。
Node pre = dummy;
while( cur != null){// 遍历当前 cur 层的节点
if(cur.left != null){
// 如果 cur.left 不为空 pre的下一个节点 就是 cur.left
// 也就说将它们串起来【填充next值】
pre.next = cur.left;
// pre 移动,为下一次链接做准备
pre = pre.next;
}
if(cur.right != null){
// 如果 cur.right 不为空 pre的下一个节点 就是 cur.right
// 也就说将它们串起来【填充next值】
pre.next = cur.right;
// pre 移动,为下一次链接做准备
pre = pre.next;
}
// cur 移动,访问这一行的下一个节点。
cur =cur.next;
}
// 前面说到 dummy 是 下一层节点的 起始位置 的 傀儡节点
// 它的next指向的节点,就是 cur 下一层的遍历的起始位置
cur = dummy.next;
}
return root;
}
}
LeetCode所有的链表题的题解都这里哦,除了vip 和 关于 Hash 的题外,几乎都在里面。 二叉树、排序、堆,栈,队列 的题,正在一步步完善。
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/DarkAndGrey/article/details/123010045
内容来源于网络,如有侵权,请联系作者删除!