leetcode练习题 populating-next-right-pointers-in-each-node

解题思路

这道题可以用树的层次遍历实现，用一个vector按层次遍历的顺序存下所有结点，用一个map存下每个结点所在的层数，之后遍历vector，若为最后一个结点或者结点与其下一结点的层次不同时就将该结点的next置为空，否则将next设为该结点按顺序的下一个兄弟结点。

代码

#include<queue>
#include<map>
class Solution {
public:void connect(TreeLinkNode *root) {queue<TreeLinkNode *>q;vector<TreeLinkNode *>v;map<TreeLinkNode *,int>m;if(root != NULL){q.push(root);m[root] = 1;}while(!q.empty()){TreeLinkNode *tmp = q.front();q.pop();v.push_back(tmp);if(tmp->left){m[tmp->left] = m[tmp] + 1;q.push(tmp->left);}if(tmp->right){m[tmp->right] = m[tmp] + 1;q.push(tmp->right);}}for(int i = 0;i < v.size();i++){if(i + 1 == v.size() || m[v[i]] != m[v[i + 1]])v[i]->next = NULL;elsev[i]->next = v[i + 1];}}
};