【题目】
Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
- You may only use constant extra space.
For example,
Given the following binary tree,
1 / \ 2 3 / \ \ 4 5 7
After calling your function, the tree should look like:
1 -> NULL / \ 2 -> 3 -> NULL / \ \ 4-> 5 -> 7 -> NULL
【分析】
无
【代码】
/********************************* * 日期:2014-12-24 * 作者:SJF0115 * 题目: 117.Populating Next Right Pointers in Each Node II * 来源:https://oj.leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/ * 结果: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); }
时间: 2024-09-16 23:13:17