LeetCode 題解 | 116. 填充每個節點的下一個右側節點指針

力扣 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)，不需要存儲額外的節點。

本文作者：力扣

聲明：本文歸“力扣”版權所有，如需轉載請聯繫。