117. Populating Next Right Pointers in Each Node II

发表于 | 分类于

每日一题 2019 - 04 - 29

题目：

Given a binary tree

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":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.

解法：

这个题是 leetcode 116 的改进版，也即这个二叉树并不是一颗满二叉树，所以需要考虑的问题更多，比如：

  • 一个结点缺少左子节点
  • 一个结点缺少右子节点
  • 一个结点同时缺少左右节点

所以这个题就不能单纯的深度遍历所有层的左子节点，所以可以更换思路为使用一个临时变量 tmp 记录当前根节点的下一个节点，通过判断下一个节点是否存在左右子节点来供当前节点连接；

同时由于要遍历到二叉树的最下层，且存在着左右子节点一方或者两方都缺失的情况，所以需要对每一层进行遍历，找到不缺失左右子节点的结点往下层遍历；

还需要注意一个地方，待连接的结点往后连接的过程要先判断右节点是否为空，因为右节点已经存在的情况下，左节点已经连接到右节点上，如果右节点不存在，那么把左节点往下继续连接；

代码：

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/*
// 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) {
        if( root == NULL )
        {
            return NULL ;
        }
        deconnect(root);
        return root ;
    }
    void deconnect(Node* root)
    {
        if(root == NULL)
        {
            return ;
        }
        Node* temp = root ;
        Node* tmp = root ; 
        while(root)
        {
            if( root -> left != NULL && root -> right != NULL)
            {
                root -> left -> next = root -> right ;
            }
            else if(root -> left == NULL && root -> right == NULL)
            {
                root = root -> next ;
                continue ;
            }
            tmp = root -> next ;
            while(tmp && tmp -> left == NULL && tmp -> right == NULL)
            {
                tmp = tmp -> next ;
            }
            if(tmp != NULL)
            {
                if(root -> right != NULL)
                {
                    if(tmp -> left != NULL)
                    {    
                        root -> right -> next = tmp -> left ;
                    }
                    else if(tmp -> right != NULL)
                    {
                        root -> right -> next = tmp -> right ;
                    }
                    else
                    {
                        root -> right -> next = NULL ;
                    }
                }
                else if(root -> left != NULL)
                {
                    if(tmp -> left != NULL)
                    {    
                        root -> left -> next = tmp -> left ;
                    }
                    else if(tmp -> right != NULL)
                    {
                        root -> left -> next = tmp -> right ;
                    }
                     else
                    {
                        root -> left -> next = NULL ;
                    }
                }
            }
            root = tmp ;
        }
        while(temp && temp->left == NULL && temp -> right == NULL )
        {
            temp = temp -> next ;
        }
        if(temp == NULL)
        {
            return ;
        }
        else if(temp -> left)
        {
            deconnect(temp->left);
        }
        else 
        {
            deconnect(temp->right);
        }
    }
};
0%
undefined