[Leetcode]Populating Next Right Pointers in Each NodeIII

这道题是很久之前做的了，leetcode中等难度的题目，想了很久没有想比较简洁的做法。就隐约记得当时是自己灵光一现想出了一个可以把这道题I和II通吃的办法，结果就是回忆不起来（I是满树，而II是普通树）。不过这道题可以肯定是做广度遍历，深度遍历要用栈，没法找到相邻元素。而广度遍历的非递归做法又要用到队列，，用一个队列或者两个队列交替来存储遍历过元素的指针，以便找到下一排元素。

翻了一下以前写过的代码，大致思路是这样的：用一个vector<TreeNode *> v来存储每一横排当前遍历到的元素指针，每一排i一个占一个数组位置v[i]，因为是广度遍历，所以每一排遍历完成时v[i]保存的是这一排最后一个元素。如果来到新的一排，则在数组中再添加一个元素，直到广度遍历完成。仔细想想这个方法可以适应任何树的形状， 不管是满树还是其他树，广度遍历的按排遍历的原则支持这个方法的正确性。

下面是代码：

class Solution {public:void connect(TreeLinkNode *root) {int i = 1;vector<TreeLinkNode *> v;connectRight(root, v,i);}void connectRight(TreeLinkNode *root,vector<TreeLinkNode *> &v,int i){if(root != NULL){if(i > v.size()){v.push_back(root);}else{v[i-1]->next = root;v[i-1] = root;}connectRight(root->left,v,i+1);connectRight(root->right,v,i+1);}}};

“人无完人金无足赤”，只要是人就不会是完美的，