首页 > 代码库 > [LeetCode]116.Populating Next Right Pointers in Each Node
[LeetCode]116.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 to NULL
.
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
Show Tags
【分析】
在层次遍历过程中,修改next指针指向。
类似于: [LeetCode]Binary Tree Level Order Traversal
【代码】
/********************************* * 日期:2014-12-24 * 作者:SJF0115 * 题目: 116.Populating Next Right Pointers in Each Node * 来源:https://oj.leetcode.com/problems/populating-next-right-pointers-in-each-node/ * 结果:AC * 来源:LeetCode * 总结: **********************************/ #include <iostream> #include <queue> using namespace std; struct TreeLinkNode { int val; TreeLinkNode *left; TreeLinkNode *right; TreeLinkNode *next; TreeLinkNode(int x):val(x),left(NULL),right(NULL),next(NULL){} }; class Solution { public: void connect(TreeLinkNode *root) { if(root == NULL){ return; }//if queue<TreeLinkNode*> cur; queue<TreeLinkNode*> next; cur.push(root); TreeLinkNode *p,*pre; while(!cur.empty()){ pre = NULL; // 当前层遍历 while(!cur.empty()){ // 出队列 p = cur.front(); cur.pop(); // 横向连接 if(pre != NULL){ pre->next = p; }//if pre = p; // next保存下一层节点 // 左子树不空加入队列 if(p->left){ next.push(p->left); }//if // 右子树不空加入队列 if(p->right){ next.push(p->right); }//if }//while p->next = NULL; swap(next,cur); }//while } }; //按先序序列创建二叉树 int CreateBTree(TreeLinkNode*& T){ int data; //按先序次序输入二叉树中结点的值,-1表示空树 cin>>data; if(data =http://www.mamicode.com/= -1){>
[LeetCode]116.Populating Next Right Pointers in Each Node
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。