Skip to content

Latest commit

 

History

History
85 lines (56 loc) · 3.56 KB

0117-populating-next-right-pointers-in-each-node-ii.adoc

File metadata and controls

85 lines (56 loc) · 3.56 KB

117. Populating Next Right Pointers in Each Node II

{leetcode}/problems/populating-next-right-pointers-in-each-node-ii/[LeetCode - Populating Next Right Pointers in Each Node II^]

Given a binary tree

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

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.

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.

Example 1:

{image_attr} 
Input: root = [1,2,3,4,5,null,7]
Output: [1,,2,3,,4,5,7,]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '' signifying the end of each level.

Constraints:

  • The number of nodes in the given tree is less than 6000.

  • -100 ⇐ node.val ⇐ 100

解题分析

这道题和 116. Populating Next Right Pointers in Each Node 算是姊妹题。

最简单的方式，使用 Deque 来保存每一层节点，然后建立起来"连接"。但是，很明显，这种方案不符合空间复杂度要求。

基于上面这种解法，再深入思考一步，上面使用 Deque 就是想要保存接下来需要访问的元素，并且保存访问的前后顺序。现在 Node 上有 next 字段，可以利用这个字段，打通这条链表，遍历上一层时，打通下一次的链接结构。这里需要保存的就有两点：

  1. 这条链表的头结点，用于下一层的遍历；

  2. 这条链表的尾节点，用于添加下一个节点。

这道题的思路和 116. Populating Next Right Pointers in Each Node 思路几乎是一样的：在上层遍历中，建立下一层的链接。

但这道题和 116. Populating Next Right Pointers in Each Node 在于：116 是完全二叉树，那么可以直接使用 next 节点的 left 子节点。这道题不是一个完全二叉树，所以，就需要在运动中寻找不为空的节点。另外，最左节点的选择，也不能直接使用 mostLeft.left，也是需要在运动中去寻找下一层第一个不为空的节点。两道题区别不大只是需要多注意细节。

{image_attr}

这样，把第一种解法的代码稍作修改就可以了。

link:{sourcedir}/_0117_PopulatingNextRightPointersInEachNodeII.java[role=include]
link:{sourcedir}/_0117_PopulatingNextRightPointersInEachNodeII_2.java[role=include]
link:{sourcedir}/_0117_PopulatingNextRightPointersInEachNodeII_21.java[role=include]