【题目】
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 == -1){ T = NULL; } else{ T = new TreeLinkNode(data); //构造左子树 CreateBTree(T->left); //构造右子树 CreateBTree(T->right); } return 0; } // 输出 void LevelOrder(TreeLinkNode *root){ if(root == NULL){ return; }//if TreeLinkNode *p = root,*q; while(p){ q = p; // 横向输出 while(q){ cout<<q->val<<"->"; q = q->next; }//while if(q == NULL){ cout<<"NULL"<<endl; }//if p = p->left; }//while } int main() { Solution solution; TreeLinkNode* root(0); CreateBTree(root); solution.connect(root); LevelOrder(root); }
【分析二】
对于一个左节点,相邻节点为父节点的右子节点。next指针指向父节点的右子节点。
对于一个当右节点稍微麻烦一些。相邻节点为父节点的右相邻节点的左子结点。父节点的右相邻节点还可能为空,所以需要判断一下。
// 父节点右相邻节点不为空 if(next){ connect(cur->right,next->left); }//if // 父节点右相邻节点为空 else{ connect(cur->right,NULL); }//else
next指针指向父节点的右相邻节点的左子结点或者空指针。
【代码二】
class Solution { public: void connect(TreeLinkNode *root) { if(root == NULL){ return; }//if connect(root,NULL); }//void private: // cur 当前节点 next 右相邻节点 void connect(TreeLinkNode *cur,TreeLinkNode *next) { if(cur == NULL){ return; }//if else{ cur->next = next; }//else // 左子树(连接的下一节点为父节点的右节点) if(cur->left){ connect(cur->left,cur->right); }//if // 右子树(连接的下一节点为父节点相邻节点的左节点) if(cur->right){ // 右相邻节点不为空 if(next){ connect(cur->right,next->left); }//if // 右相邻节点为空 else{ connect(cur->right,NULL); }//else }//if }//void };
时间: 2024-09-05 23:22:57