今日算法之_163_填充每个节点的下一个右侧节点指针
前言
Github:https://github.com/HealerJean
1、填充每个节点的下一个右侧节点指针_1
给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。
初始状态下,所有 next 指针都被设置为 NULL。
1.1、解题思路
看代码吧
1.2、算法
1.2.1、算法1:队列
/**
* 方法1 层序遍历
* @param root
* @return
*/
public Node connect(Node root) {
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
Node next = null;
while (size > 0) {
size--;
Node node = queue.remove();
//因为是满二叉树,所以如果有一个为空则退出
if (node == null){
break;
}
queue.add(node.right);
queue.add(node.left);
//赋值
node.next = next;
next = node;
}
}
return root;
}
1.2.2、算法1:官方递归
/**
* 官方解答(有点像翻转二叉树)
* @param root
* @return
*/
public Node connect(Node root) {
//如果满足以下条件任何一种说明已经在最后一行了(后面两个只要判断一种就可以)
//root == null 只判断第一个节点
if (root == null || root.left == null || root.right == null ) {
return root;
}
//连接孩子结点,连接右孩子需要注意,如果root的next为null,则右孩子的next为null,否则为root.next的left
Node left = root.left;
Node right = root.right;
left.next = right;
//从上到下执行的,所以即使将右节点的next确定
if (root.next != null) {
right.next = root.next.left;
}
//不会执行到最后一行的
connect(left);
connect(right);
return root;
}
1.3、测试
@Test
public void test(){
System.out.println(connect(initNode()));
}
public Node initNode(){
Node node7 = new Node(7, null, null, null);
Node node6 = new Node(6, null, null, null);
Node node5 = new Node(5, null, null, null);
Node node4 = new Node(4, null, null, null);
Node node3 = new Node(3, node6, node7, null);
Node node2 = new Node(2, node4, node5, null);
Node node1 = new Node(1, node2, node3, null);
return node1 ;
}
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int val) {
this.val = val;
}
public Node(int val, Node left, Node right, Node next) {
this.val = val;
this.left = left;
this.right = right;
this.next = next;
}
}
2、填充每个节点的下一个右侧节点指针_2
给定一个二叉树,填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。
初始状态下,所有 next 指针都被设置为 NULL。
2.1、解题思路
看算法吧
2.2、算法
2.2.1、算法1:队列
/**
* 方法1 层序遍历
* @param root
* @return
*/
public Node connect1(Node root) {
if (root == null){
return root;
}
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
Node next = null;
while (size > 0) {
size--;
Node node = queue.remove();
if (node.right != null){
queue.add(node.right);
}
if (node.left != null){
queue.add(node.left);
}
//赋值
node.next = next;
next = node;
}
}
return root;
}
2.2.2、算法1:官方递归
/**
* 方法2:官方解答
* @param root
* @return
*/
public Node connect(Node root) {
if(root == null){
return root;
}
Node curLineNode = root;
while (curLineNode != null){
//构建下一行的链表
Node nextLineNode = new Node(-1);
Node nextPre = nextLineNode;
//然后开始遍历当前层的链表
while (curLineNode != null){
//如果当前节点的左子节点不为空,就让pre节点的next指向他,也就是把它串起来
if (curLineNode.left != null){
nextPre.next = curLineNode.left;
nextPre = nextPre.next;
}
if (curLineNode.right != null){
nextPre.next = curLineNode.right;
nextPre = nextPre.next;
}
//继续访问这一行的下一个节点
curLineNode = curLineNode.next;
}
//把下一层串联成一个链表之后,让他赋值给cur,后续继续循环,直到cur为空为止
curLineNode = nextLineNode.next;
}
return root;
}
2.3、测试
@Test
public void test(){
System.out.println(connect(initNode()));
}
public Node initNode(){
Node node7 = new Node(7, null, null, null);
Node node6 = new Node(6, null, null, null);
Node node5 = new Node(5, null, null, null);
Node node4 = new Node(4, null, null, null);
Node node3 = new Node(3, node6, node7, null);
Node node2 = new Node(2, node4, node5, null);
Node node1 = new Node(1, node2, node3, null);
return node1 ;
}
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int val) {
this.val = val;
}
public Node(int val, Node left, Node right, Node next) {
this.val = val;
this.left = left;
this.right = right;
this.next = next;
}
}