首页 > 代码库 > [leetcode]Populating Next Right Pointers in Each Node
[leetcode]Populating Next Right Pointers in Each Node
问题描述:
Given a binary tree
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set toNULL
.
Initially, all next pointers are set to NULL
.
Note:
- You may only use constant extra space.
- You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,
1
/ 2 3
/ \ / 4 5 6 7
After calling your function, the tree should look like:
1 -> NULL
/ 2 -> 3 -> NULL
/ \ / 4->5->6->7 -> NULL
基本思路:
用队列保存需要链接的同层节点。
代码:
void connect(TreeLinkNode *root) { if(root == NULL) return; queue<TreeLinkNode*> _queue; _queue.push(root); TreeLinkNode head(0); TreeLinkNode* pre = &head; queue<TreeLinkNode*> second; while(!_queue.empty()) { TreeLinkNode* tmp = _queue.front(); _queue.pop(); if(tmp->left != NULL) second.push(tmp->left); if(tmp->right != NULL) second.push(tmp->right); if(_queue.empty()) { pre->next = tmp; tmp->next = NULL; pre = &head; while(!second.empty()) { _queue.push(second.front()); second.pop(); } } else { pre->next = tmp; pre = tmp; } } // return root; }
[leetcode]Populating Next Right Pointers in Each Node
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。