LeetCode117：填充每個節點的下一個右側節點指針 II

2020 年 2 月 26 日
筆記

LeetCode117：填充每個節點的下一個右側節點指針 II Populating Next Right Pointers in Each Node II

題目：

給定一個二叉樹

Given a binary tree

struct Node {    int val;    Node *left;    Node *right;    Node *next;  }

填充它的每個 next 指針，讓這個指針指向其下一個右側節點。如果找不到下一個右側節點，則將 next 指針設置為 NULL。

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

初始狀態下，所有 next 指針都被設置為 NULL。

Initially, all next pointers are set to NULL.

進階：

你只能使用常量級額外空間。
使用遞歸解題也符合要求，本題中遞歸程式佔用的棧空間不算做額外的空間複雜度。

Follow up:

You may only use constant extra space.
Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.

示例：

img

輸入：root = [1,2,3,4,5,null,7]  輸出：[1,#,2,3,#,4,5,7,#]  解釋：給定二叉樹如圖 A 所示，你的函數應該填充它的每個 next 指針，以指向其下一個右側節點，如圖 B 所示。

提示：

樹中的節點數小於 6000
-100 <= node.val <= 100 Constraints:
The number of nodes in the given tree is less than 6000.
-100 <= node.val <= 100

解題思路：

與上一題的唯一區別就是該二叉樹不是完美二叉樹。對於完美二叉樹的思路：

一個結點的左孩子的 next 指針指向該結點的右孩子
一個結點的右孩子的 next 指針指向該結點的 next 結點的左孩子

不再適用，因為一個結點可能沒有左孩子或者沒有右孩子。只需稍微轉變一下思路即可:

先設置一個頭結點 temp，作為每層的最左側結點。再設置一個前驅結點 prev = temp，該結點的 next 指針指向最鄰近的右側結點，然後刷新前驅結點：prev = prev.next 。繼續查找 prev 結點最鄰近的右側結點，重複上述操作，直到該層結束。而此時頭結點 temp.next 就是下一層的最左側結點。

Java：

class Solution {      public Node connect(Node root) {            if (root == null)              return root;          Node temp = new Node(0); // 虛擬頭結點          Node curr = root, prev = temp; // 當前結點和前驅結點            while (curr != null) {              if (curr.left != null) {                  prev.next = curr.left;                  prev = prev.next;              }              if (curr.right != null) {                  prev.next = curr.right;                  prev = prev.next;              }              curr = curr.next;              // curr 為 null 時，該層連接完成。              if (curr == null) {                  curr = temp.next; // 當前結點改為下一層的最左側結點                  temp.next = null; // 虛擬結點 next 指針指向 null                  prev = temp; // 前驅結點重新設置為虛擬頭結點              }          }          return root;      }  }

Python：

class Solution:      def connect(self, root: 'Node') -> 'Node':          if not root:              return root          temp = Node(0) # 虛擬頭結點          prev,curr = temp,root # 當前結點和前驅結點            while curr:              if curr.left:                  prev.next = curr.left                  prev = prev.next              if curr.right:                  prev.next = curr.right                  prev = prev.next              curr = curr.next              # curr 為 null 時，該層連接完成              if not curr:                  curr = temp.next # 當前結點改為下一層的最左側結點                  temp.next = None # 虛擬結點 next 指針指向 null                  prev = temp # 前驅結點重新設置為虛擬頭結點          return root