LeetCode 116: 填充每個節點的下一個右側節點指針

2020 年 2 月 26 日
筆記

LeetCode 116: 填充每個節點的下一個右側節點指針 Populating Next Right Pointers in Each Node

題目:

給定一個完美二叉樹，其所有葉子節點都在同一層，每個父節點都有兩個子節點。二叉樹定義如下：

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

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.

示例：

img

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

提示：

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

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.

提示：

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

解題思路:

最簡單的方法就是層序遍歷二叉樹，把各個結點的next指針按要求連起來即可。題目要求不允許佔用額外空間，但是遞歸空間佔用不算在內，所以可以遞歸方法的層序遍歷解題，很簡單可以參考之前的文章：

二叉數的層序遍歷

這裡介紹另一種巧妙的解法：利用已構建的next指針解題。

核心思路只有兩個：

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

即：

node.left.next=node.right;  node.right.next=node.next.left;

剩下的無非就是判斷該結點是否為空結點，或值是否為該層結點的最後一個結點，而後進入下一層重複操作。

Java：

class Solution {      public Node connect(Node root) {          if(root == null)              return root;          // 記錄每層的最左結點，該層遍歷結束後利用最左側結點進入下一層          Node most_left = root;          Node node = root;          while(most_left.left!=null){// 最左側結點的下一層只要存在結點，則繼續操作              if(node.left != null)                  node.left.next=node.right;              if(node.next != null){ // 判斷該結點是否為該層的最後一個結點                  node.right.next = node.next.left;                  node = node.next; // 刷新該結點為 next 結點              }else{                  most_left = most_left.left; // 刷新最左側結點                  node = most_left;              }          }          return root;      }  }

Python：

class Solution:      def connect(self, root: 'Node') -> 'Node':          if not root:              return root          # 記錄每層的最左結點，該層遍歷結束後利用最左側結點進入下一層          most_left = root          node = root          while most_left.left: # 最左側結點的下一層只要存在結點，則繼續操作              if node.left:                  node.left.next = node.right              if node.next: # 判斷該結點是否為該層的最後一個結點                  node.right.next = node.next.left                  node = node.next # 刷新該結點為 next 結點              else:                  node = most_left.left # 刷新最左側結點                  most_left = node          return root