這題拖了好幾天，一直沒(méi)想明白是啥意思，今天突然猜想到題意，竟然就過(guò)了...
題目所說(shuō)的指向下一個(gè)右指針就是層次遍歷，找到每個(gè)節(jié)點(diǎn)同層的下一個(gè)節(jié)點(diǎn)...=，=
于是只要層次遍歷這棵二叉樹(shù)[BFS]，對(duì)每一層的節(jié)點(diǎn)用depth記錄深度，找隊(duì)列里同一層的下一個(gè)節(jié)點(diǎn)就行
PS: 這題是Populating Next Right Pointers in Each Node的強(qiáng)化版，自然，這個(gè)代碼兩題都可AC的
1 /**
2 * Definition for binary tree with next pointer.
3 * struct TreeLinkNode {
4 * int val;
5 * TreeLinkNode *left, *right, *next;
6 * TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
7 * };
8 */
9
10
11
12 class Solution {
13 public:
14 struct Queue {
15 int depth;
16 TreeLinkNode* t;
17 }que[100010];
18
19 void connect(TreeLinkNode *root) {
20 if(root == NULL) return;
21 int l = 0, r = 1, k = 0, tpdepth = 0;
22 que[0].t = root;
23 que[0].depth = 0;
24 while(l < r) {
25 TreeLinkNode *tp = que[l].t;
26 if(que[l].depth > tpdepth) {
27 for(;k < l - 1; ++k) {
28 que[k].t->next = que[k + 1].t;
29 }
30 ++k;
31 tpdepth++;
32 }
33 if(tp->left != NULL) {
34 que[r].t = tp->left;
35 que[r].depth = que[l].depth + 1;
36 ++r;
37 }
38 if(tp->right != NULL) {
39 que[r].t = tp->right;
40 que[r].depth = que[l].depth + 1;
41 ++r;
42 }
43 ++l;
44 }
45 for(;k < l - 1; ++k) {
46 que[k].t->next = que[k + 1].t;
47 }
48 }
49 };