Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
这题拖了好几天,一直没想明白是啥意思,今天突然猜想到题意,竟然就过了...
题目所说的指向下一个右指针就是层次遍历,找到每个节点同层的下一个节点...=,=
于是只要层次遍历这棵二叉树[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 };

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理