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