二叉树|116.填充每个节点的下一个右侧节点指针 117. 填充每个节点的下一个右侧节点指针 II

本文主要是介绍二叉树|116.填充每个节点的下一个右侧节点指针 117. 填充每个节点的下一个右侧节点指针 II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

116.填充每个节点的下一个右侧节点指针

题目： 给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。、
初始状态下，所有 next 指针都被设置为 NULL。
在这里插入图片描述

题目链接： 116.填充每个节点的下一个右侧节点指针
用层次遍历解决即可该代码可解决117的问题

//层次遍历
class Solution {public Node connect(Node root) {Queue<Node> myqueue=new LinkedList<>();if(root==null){return root;}myqueue.offer(root);while(!myqueue.isEmpty()){int num=myqueue.size();while(num>0){Node tempNode=myqueue.poll();if(tempNode.left!=null){myqueue.offer(tempNode.left);}if(tempNode.right!=null){myqueue.offer(tempNode.right);}if(num==1){tempNode.next=null;}else{tempNode.next=myqueue.peek();}num--;}}return root;}
}

完美二叉数的另一种解法（这里一定要注意是完美二叉树）
其他解法：同一个父亲的节点可以通过父节点链接不同父亲的最左子节点和最右子节点通过父节点的next链接进行连接最终的终止条件是节点的左节点不为空(说明到达最后一层)

class Solution {public Node connect(Node root) {if (root == null) {return root;}// 从根节点开始Node leftmost = root;while (leftmost.left != null) {// 遍历这一层节点组织成的链表，为下一层的节点更新 next 指针Node head = leftmost;while (head != null) {// CONNECTION 1head.left.next = head.right;// CONNECTION 2if (head.next != null) {head.right.next = head.next.left;}// 指针向后移动head = head.next;}// 去下一层的最左的节点leftmost = leftmost.left;}return root;}
}

117.填充每个节点的下一个右侧节点指针||

第二种解决方式在当前层为下一层创建链表到下一层是使用虚拟头节点->next获取下一层链表的节点循环构建下一层的链表

class Solution {public Node connect(Node root) {Node dummy = new Node();Node cur = root;while (cur != null) {dummy.next = null;Node nxt = dummy; // 下一层的链表while (cur != null) { // 遍历当前层的链表if (cur.left != null) {nxt.next = cur.left; // 下一层的相邻节点连起来nxt = cur.left;}if (cur.right != null) {nxt.next = cur.right; // 下一层的相邻节点连起来nxt = cur.right;}cur = cur.next; // 当前层链表的下一个节点}cur = dummy.next; // 下一层链表的头节点}return root;}
}