leetcode-jecklee/PopulatingNextRightPointersInEachNodeII.cpp at master · rainlee/leetcode-jecklee · GitHub

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         God Bless Me     BUG Free Forever
*/
/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
/***
 * 按层遍历，统一适用于Populating Next Right Pointers in Each Node
 * 时间复杂度O(n) 空间复杂度O(n)
 ***/
/*
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (NULL == root)
            return;

        queue<TreeLinkNode *> qtree;
        qtree.push(root);
        TreeLinkNode *node = root;
        TreeLinkNode *pre = NULL;
        int n1 = 1;
        int n2 = 0;
        int cnt = 0;
        while (!qtree.empty())
        {
            node = qtree.front();
            qtree.pop();

            if (node->left)
            {
                qtree.push(node->left);
                ++n2;
            }
            if (node->right)
            {
                qtree.push(node->right);
                ++n2;
            }

            if (pre)
                pre->next = node;

            if (++cnt == n1) // end of this level
            {
                pre = NULL;
                n1 = n2;
                n2 = 0;
                cnt = 0;
            }
            else
                pre = node;
        }
        return;
    }
};
*/

/***
 * 法2：递归
 * 一层一层处理，标记该层第一个节点first和前一个处理过的节点last
 * 先处理左孩子，后处理右孩子，然后处理父节点的next
 * 处理完一层(root->next == NULL)，递归处理first
 * 时间复杂度O(n) 空间复杂度O(logn)
 ***/
/*
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (NULL == root)
            return;

        TreeLinkNode dummy(-1);  // first node
        TreeLinkNode *node = root;
        TreeLinkNode *pre = &dummy;
        while (node)
        {
            if (node->left)
            {
                pre->next = node->left;
                pre = pre->next;
            }
            if (node->right)
            {
                pre->next = node->right;
                pre = pre->next;
            }
            node = node->next;   // next node in this level
        }
        connect(dummy.next);     // next level
    }
};
*/

/***
 * 法3：法2的尾递归改迭代
 * 两层循环，外层循环遍历行，内层循环处理每行的LinkList
 * 时间复杂度O(n) 空间复杂度O(1)
 ***/
class Solution {
public:
    void connect(TreeLinkNode *root) {
        TreeLinkNode *node = root;
        while (node)
        {
            TreeLinkNode dummy(-1);   // head of this level
            TreeLinkNode *level = node;
            TreeLinkNode *pre = &dummy;
            while (level)
            {
                if (level->left)
                {
                    pre->next = level->left;
                    pre = pre->next;
                }
                if (level->right)
                {
                    pre->next = level->right;
                    pre = pre->next;
                }
                level = level->next;   // next node in this level
            }
            node = dummy.next;   // next level
        }
    }
};