Posted on 2014-01-10 18:26
Uriel 阅读(106)
评论(0) 编辑 收藏 引用 所属分类:
LeetCode
这题拖了好几天，一直没想明白是啥意思，今天突然猜想到题意，竟然就过了...
题目所说的指向下一个右指针就是层次遍历，找到每个节点同层的下一个节点...=，=
于是只要层次遍历这棵二叉树[BFS]，对每一层的节点用depth记录深度，找队列里同一层的下一个节点就行
PS: 这题是Populating Next Right Pointers in Each Node的强化版，自然，这个代码两题都可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 };