3a5007f29fb5e667e14a2eb4531d2c56
(难度Medium) Problem 116. Populating Next Right Pointers in Each Node(二叉树的右兄弟)

Populating Next Right Pointers in Each Node

Difficulty

Medium

Description

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;
}

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.

Example:

Input: {"$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}

Output: {"$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}

## Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B.

Note:

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

题意

给定一棵完美二叉树,每个节点除了左右孩子之外,还多了一个next元素。我们需要把next设置成它右边的元素。

需要注意,只能使用常数级的额外空间。可以使用递归,递归的系统栈的空间不会被计算在内。

题解

一开始我没有看到常数级的内存要求的限制, 所以第一个想法就是一层一层地操作。将每一层的元素从左到右存储在一个vector当中,我们每次遍历一层的元素,遍历完成之后就可以给其中的每一个元素设置next,同时可以获取到下一层的所有元素。

其实就是化用了宽度优先搜索,因为如果直接使用宽搜的话, 我们区分层次信息会比较麻烦。

更多细节,可以查看代码:

top Created with Sketch.