problem:
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
Hide Tags
TreeDepth-first Search
题意:是上一题的普适版,不要求满树!每层节点链接起来,类似B*树
thinking:
(1)上一题说过,,采用BFS 而不是DFS:
(2)采用queue结构存储每层的结点
code:
class Solution {public:void connect(TreeLinkNode *root) {if(root==NULL)return;queue<TreeLinkNode*> queue0;queue0.push(root);level_visit(queue0);return;}protected:void level_visit(queue<TreeLinkNode*> queue1){if(queue1.empty())return;queue<TreeLinkNode*> queue2=queue1;queue<TreeLinkNode*> queue3;TreeLinkNode *tmp=queue1.front();queue1.pop();tmp->next=NULL;while(!queue1.empty()){TreeLinkNode *tmp2=queue1.front();queue1.pop();tmp2->next=NULL;tmp->next=tmp2;tmp=tmp2;}while(!queue2.empty()){TreeLinkNode *node=queue2.front();queue2.pop();if(node->left!=NULL)queue3.push(node->left);if(node->right!=NULL)queue3.push(node->right);}level_visit(queue3);}};
其实你已经错过了旅行的意义。