81204cf4a3582d33711f750d0d4c1027
(难度Medium) Problem 117. Populating Next Right Pointers in Each Node II(二叉树求右边元素)

Populating Next Right Pointers in Each Node II

Difficulty

Medium

Description

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.

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":null,"next":null,"right":{"$id":"6","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":null,"right":null,"val":7},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"6","left":null,"next":null,"right":{"$ref":"5"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"6"},"val":1}

## 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.

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指针当中。

要求只能开辟常数级的空间。

题解

这题看起来和之前的那题差不多,只有一个小小的变化。那就是在之前的题目当中,给定的是完美二叉树,而这题中不是,就是一棵普通的二叉树。

看似差别不大,其实不然,二叉树不是完美的会导致一个严重的问题。

什么问题呢?

假设x是二叉树当中的某一个元素,当我求x.right的next的时候,就有问题了。在完美二叉树当中,我们可以直接讲x.next.left赋值给x.right.next,这是因为二叉树是完美的。x.next.left一定存在。如果x.next.left不存在呢?那么我们应该继续往右找,再找下一个next。

​      x                y               z

​        \                                  \

​          a                                 b

在这个例子当中,x的next是y,但是y很有可能没有孩子。那么我们需要继续找到y的next,将它的最左侧的元素赋值给a的next。如果y的next也没有孩子,那么我们要继续往右遍历,一直到找到或者是结束为止。

top Created with Sketch.