2021-07-14（116、117. 填充每个节点的下一个右侧节点指针）

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

首先用队列，层次遍历是两题都可以的。但空间复杂度太高。

/*
// 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 null;}Queue<Node> queue=new LinkedList<>();queue.offer(root);while(!queue.isEmpty()){int size=queue.size();for(int i=0;i<size;++i){Node temp=queue.poll();if(i<size-1){temp.next=queue.peek();}if(temp.left!=null){queue.offer(temp.left);}if(temp.right!=null){queue.offer(temp.right);}}}return root;}
}

当年做题不认真，该用的时候就傻眼了。空间复杂度低的方法也不会。队列怎么用也忘了。其实每个节点的next指针本质和队列是一样的，都是保存同一层的下一个节点
下面是完美二叉树的情况：

/*
// 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 null;}Node mostLeft=root;while(mostLeft.left!=null){Node temporary=mostLeft;while(temporary!=null){temporary.left.next=temporary.right;if(temporary.next!=null){temporary.right.next=temporary.next.left;}temporary=temporary.next;}mostLeft=mostLeft.left;}return root;}
}

自己想从完美二叉树的情况推，也没推出来。学习学习题解了，发现核心还是：记录好最左边节点的同时，也记录好last。不过就是记录的方法更复杂了。
下面是普通二叉树的情况：

/*
// 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 null;}Node mostLeft=root;Node temporary;Node nextMostLeft;Node last;while(mostLeft!=null){temporary=mostLeft;nextMostLeft=null;last=null;while(temporary!=null){if(temporary.left!=null){if(nextMostLeft==null){nextMostLeft=temporary.left;}if(last!=null){last.next=temporary.left;}last=temporary.left;}if(temporary.right!=null){if(nextMostLeft==null){nextMostLeft=temporary.right;}if(last!=null){last.next=temporary.right;}last=temporary.right;}temporary=temporary.next;}mostLeft=nextMostLeft;}return root;}
}