116. Populating Next Right Pointers in Each Node

发表于 | 分类于

每日一题 2019 - 04 - 28

题目：

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:

1
2
3
4
5
6
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:

img

1
2
3
4
5
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.

解法：

这个题让把一颗二叉树的每一层的每个结点之间都以链表的形式连接起来，最直观的思路就是使用层次遍历的方法，但是需要注意一个问题，这个题中不能使用额外的空间进行处理，所以就考虑放弃使用队列来解决问题，考虑使用递归的方法：

  • 深层次进入二叉树的最左下的子节点，从左子节点开始进行连接
  • 由于这是一颗满二叉树，所以除了每一层的最左边与最右边，一定相邻之间存在节点，所以通过上层结点直接进行连接即可；

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() {}

    Node(int _val, Node* _left, Node* _right, Node* _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/
class Solution {
public:
    Node* connect(Node* root) {
        deconnect(root);
        return root ;
    }
    void deconnect(Node *root)
    {
       if( root == NULL || root -> left == NULL)
       {
           return;
       } 
       Node* temp = root ;
       while(root)
       {
           root -> left -> next = root -> right ;
           if(root-> next)
           {
               root -> right -> next = root -> next -> left;
           }
           root = root -> next ;
       }
       connect(temp -> left);
    }
};
0%
undefined