力扣 116. 填充每個節點的下一個右側節點指針 （點擊文末閱讀原文查看題目）
題目描述
給定一個完美二叉樹，其所有葉子節點都在同一層，每個父節點都有兩個子節點。二叉樹定義如下：
<code>struct Node {
int val;
Node *left;
Node *right;
Node *next;
}/<code>填充它的每個 next 指針，讓這個指針指向其下一個右側節點。如果找不到下一個右側節點，則將 next 指針設置為 NULL。
初始狀態下，所有 next 指針都被設置為 NULL。
示例：
<code>輸入：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}
輸出：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}
解釋：給定二叉樹如圖 A 所示，你的函數應該填充它的每個 next 指針，以指向其下一個右側節點，如圖 B 所示。/<code>提示：
- 你只能使用常量級額外空間。
- 使用遞歸解題也符合要求，本題中遞歸程序佔用的棧空間不算做額外的空間複雜度。
解決方案
方法一：層序遍歷
思路
樹和圖的兩種基本遍歷方法。一種是深度優先方法，例如：每次只遍歷一個分支；另外一種是廣度優先方法，例如：先遍歷完這一層再進入下一層。樹的深度優先遍歷又可以分為先序遍歷 preorder、中序遍歷 inorder 和後序遍歷postorder。樹的廣度優先遍歷基於節點的層級 level 概念。一個節點的層級取決於該節點的深度或者到根節點的距離。需要先遍歷完同一層級的所有節點，才能進入下一層級。
很明顯，此問題應該使用廣度優先遍歷解決。使用廣度優先遍歷，可以將同一層級的所有節點連接起來。
算法
1.創建一個輔助隊列 Q，可以通過多種方式實現層序遍歷，尤其是在在識別特定節點的時候。
1.在隊列中以（node,level) 的形式存儲節點，同時存儲其子節點為 (node.left，parent_level + 1) 和 (node.right，parent_level + 1)。這種方法節點多了一個層級屬性，需要創建一個新的數據結構，效率很低。
2.可以使用一個標記分離不同層級之間的節點。通常情況下，在隊列中插入一個 NULL 元素，標記當前層級結束，下一層級開始。但是這種方法會創建與層級數量相同個數的 NULL 元素，造成過多內存消耗。
3.該方法使用嵌套循環結構，避免了方法二中的 NULL 元素。該方法的每一步都需要記錄當前隊列中 全部 元素數量，對應樹中一個層級元素的數量。然後從隊列中處理對應數量的元素。完成後，這一層級所有的節點都被訪問，隊列包含下一層級的 全部 節點。下面是對應偽代碼：
Python 實現
<code>while (!Q.empty())
{
size = Q.size()
for i in range 0..size
{
node = Q.pop()
Q.push(node.left)
Q.push(node.right)
}
}/<code>2.首先在隊列中加入根節點。因為第 0 層級只有一個節點，不需要建立連接，直接進入 while 循環即可。
3.偽代碼中 while 循環迭代的是樹的層級，內部的 for 循環迭代的是一個層級上所有的節點。由於可以訪問同一層級的所有節點，因此能夠建立指針連接。
4. for 循環彈出一個節點時，同時把它的孩子節點加入隊列。因此隊列中每個層級的元素也是順序存儲的。可以通過已有的順序建立 next 指針。
Java 實現
<code>class Solution {
public Node connect(Node root) {
if (root == null) {
return root;
}
// Initialize a queue data structure which contains
// just the root of the tree
Queue Q = new LinkedList();
Q.add(root);
// Outer while loop which iterates over
// each level
while (Q.size() > 0) {
// Note the size of the queue
int size = Q.size();
// Iterate over all the nodes on the current level
for(int i = 0; i < size; i++) {
// Pop a node from the front of the queue
Node node = Q.poll();
// This check is important. We don't want to
// establish any wrong connections. The queue will
// contain nodes from 2 levels at most at any
// point in time. This check ensures we only
// don't establish next pointers beyond the end
// of a level
if (i < size - 1) {
node.next = Q.peek();
}
// Add the children, if any, to the back of
// the queue
if (node.left != null) {
Q.add(node.left);
}
if (node.right != null) {
Q.add(node.right);
}
}
}
// Since the tree has now been modified, return the root node
return root;
}
}/<code>Python 實現
<code>import collections
class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root:
return root
# Initialize a queue data structure which contains
# just the root of the tree
Q = collections.deque([root])
# Outer while loop which iterates over
# each level
while Q:
# Note the size of the queue
size = len(Q)
# Iterate over all the nodes on the current level
for i in range(size):
# Pop a node from the front of the queue
node = Q.popleft()
# This check is important. We don't want to
# establish any wrong connections. The queue will
# contain nodes from 2 levels at most at any
# point in time. This check ensures we only
# don't establish next pointers beyond the end
# of a level
if i < size - 1:
node.next = Q[0]
# Add the children, if any, to the back of
# the queue
if node.left:
Q.append(node.left)
if node.right:
Q.append(node.right)
# Since the tree has now been modified, return the root node
return root/<code>複雜度分析
- 時間複雜度：O(N) 。每個節點被訪問一次，即從隊列中彈出，並建立 next 指針。
- 空間複雜度：O(N) 。這是一棵完美二叉樹，它的最後一個層級包含 N / 2 個節點。廣度優先遍歷的複雜度取決於一個層級上的最大元素數量。這種情況下空間複雜度為 O(N) 。
方法二：使用已建立的 next 指針
思路
一棵樹中，存在兩種類型的 next 指針。
1.第一種情況是連接同一個父節點的兩個子節點。它們可以通過同一個節點直接訪問到，因此執行下面操作即可完成連接。
Java 實現
<code>node.left.next = node.right/<code>
2.第二種情況在不同父親的子節點之間建立連接，這種情況不能直接連接。
如果每個節點有指向父節點的指針，可以通過該指針找到 next 節點。如果不存在該指針，則按照下面思路建立連接：
第 N 層節點之間建立 next 指針後，再建立第 N+1 層節點的 next 指針。可以通過 next 指針訪問同一層的所有節點，因此可以使用第 N 層的 next 指針，為第 N+1 層節點建立 next 指針。
算法
1.從根節點開始，由於第 0 層只有這一個節點，所以不需要連接。直接為第 1 層節點建立 next 指針即可。該算法中需要注意的一點是，當我們為第 N 層節點建立 next 指針時，處於第 N - 1 層。當第 N 層節點的 next 指針全部建立完成後，移至第 N 層，建立第 N + 1 層節點的 next 指針。
2.遍歷某一層的節點時，這層節點的 next 指針已經建立。因此我們只需要知道這一層的最左節點，就可以按照鏈表方式遍歷，不需要使用隊列。
3.上面思路的偽代碼如下：
Java 實現
<code>leftmost = root
while (leftmost.left != null)
{
head = leftmost
while (head.next != null)
{
1) Establish Connection 1
2) Establish Connection 2 using next pointers
head = head.next
}
leftmost = leftmost.left
/<code> 
4.兩種類型的 next 指針，
1.第一種情況兩個子節點屬於同一個父節點，因此直接通過父節點建立兩個子節點的 next 指針即可。
Java 實現
<code>node.left.next = node.right/<code>
2.第二種情況是連接不同父節點之間子節點的情況。更具體地說，連接的是第一個父節點的右孩子和第二父節點的左孩子。由於已經在父節點這一層建立了 next 指針，因此可以直接通過第一個父節點的 next 指針找到第二個父節點，然後在它們的孩子之間建立連接。
Java 實現
<code>node.right.next = node.next.left/<code>
完成當前層的連接後，進入下一層重複操作，直到所有的節點全部連接。進入下一層後需要更新最左節點，然後從新的最左節點開始遍歷該層所有節點。因為是完美二叉樹，因此最左節點一定是當前層最左節點的左孩子。如果當前最左節點的左孩子不存在，說明已經到達該樹的最後一層，完成了所有節點的連接。
Java 實現
<code>class Solution {
public Node connect(Node root) {
if (root == null) {
return root;
}
// Start with the root node. There are no next pointers
// that need to be set up on the first level
Node leftmost = root;
// Once we reach the final level, we are done
while (leftmost.left != null) {
// Iterate the "linked list" starting from the head
// node and using the next pointers, establish the
// corresponding links for the next level
Node head = leftmost;
while (head != null) {
// CONNECTION 1
head.left.next = head.right;
// CONNECTION 2
if (head.next != null) {
head.right.next = head.next.left;
}
// Progress along the list (nodes on the current level)
head = head.next;
}
// Move onto the next level
leftmost = leftmost.left;
}
return root;
}
}/<code>Python 實現
<code>class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root:
return root
# Start with the root node. There are no next pointers
# that need to be set up on the first level
leftmost = root
# Once we reach the final level, we are done
while leftmost.left:
# Iterate the "linked list" starting from the head
# node and using the next pointers, establish the
# corresponding links for the next level
head = leftmost
while head:
# CONNECTION 1
head.left.next = head.right
# CONNECTION 2
if head.next:
head.right.next = head.next.left
# Progress along the list (nodes on the current level)
head = head.next
# Move onto the next level
leftmost = leftmost.left
return root /<code>複雜度分析
- 時間複雜度：O(N)，每個節點只訪問一次。
- 空間複雜度：O(1)，不需要存儲額外的節點。
本文作者：力扣
聲明：本文歸“力扣”版權所有，如需轉載請聯繫。
