Posted on 2014-01-10 18:26
Uriel 閱讀(124)
評論(0) 編輯 收藏 引用 所屬分類:
LeetCode
這題拖了好幾天，一直沒想明白是啥意思，今天突然猜想到題意，竟然就過了...
題目所說的指向下一個右指針就是層次遍歷，找到每個節(jié)點(diǎn)同層的下一個節(jié)點(diǎn)...=，=
于是只要層次遍歷這棵二叉樹[BFS]，對每一層的節(jié)點(diǎn)用depth記錄深度，找隊(duì)列里同一層的下一個節(jié)點(diǎn)就行
PS: 這題是Populating Next Right Pointers in Each Node的強(qiáng)化版，自然，這個代碼兩題都可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 };