leecode 解题总结：117. Populating Next Right Pointers in Each Node II

#include <iostream>#include <stdio.h>#include <vector>#include <string>#include <sstream>#include <queue>using namespace std;/*问题: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    7After calling your function, the tree should look like:         1 -> NULL       /  /      2 -> 3 -> NULL     / /    /    4-> 5 -> 7 -> NULL关键:分析:此题和之前的题目不同在于给定的是任意二叉树，也就是说可能存在某些结点没有孩子或者只有1个孩子。这种情况最好就是用层序遍历来做，如果用之前的递归来做会存在可能两个结点中间有多个结点都没有，这样就无法连接。用层序遍历。遍历每一层的结点，然后将同一层的结点放在一起，然后设置结点指向*/void print(vector<string>& result){	if(result.empty())	{		cout << "no result" << endl;		return;	}	int size = result.size();	for(int i = 0 ; i < size ; i++)	{		cout << result.at(i) << ", " ;	}	cout << endl;}struct TreeLinkNode { int val; TreeLinkNode *left, *right, *next; TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {} TreeLinkNode() : left(NULL), right(NULL), next(NULL) {} };class Solution {public:	//层序遍历	void levelVisit(TreeLinkNode* root)	{		if(!root)		{			return;		}		queue<TreeLinkNode*> nodes;		nodes.push(root);		int size = 1;		int nextSize = 0;		TreeLinkNode* node;		vector<TreeLinkNode*> result;		vector< vector<TreeLinkNode*> > results;		//先找到每一层的起始结点，也就是size=0的结点，然后对每个起始结点遍历即可		while(!nodes.empty())		{			node = nodes.front();			nodes.pop();			result.push_back(node);			if(node->left)			{				nodes.push(node->left);				nextSize++;			}			if(node->right)			{				nodes.push(node->right);				nextSize++;			}			size--;			if(0 == size)			{				size = nextSize;				nextSize = 0;				vector<TreeLinkNode*> tempResult(result);				results.push_back(tempResult);				result.clear();			}		}		if(results.empty())		{			return;		}		int len = results.size();		TreeLinkNode* head = NULL;		vector<string> strResult;		for(int i = 0 ; i < len ; i++)		{			size = results.at(i).size();			//stringstream stream;			//stream << results.at(i).at(0)->val << "->";			for(int j = 1 ; j < size ; j++)			{				results.at(i).at(j-1)->next = results.at(i).at(j);				//stream << results.at(i).at(j)->val << "->";			}			//stream << "NULL";			//strResult.push_back(stream.str());		}		//print(strResult);	}    void connect(TreeLinkNode *root) {		//根节点为空，不需要处理        if(!root)		{			return;		}		//接下来设置根节点自己的next指针为null		root->next = NULL;		//递归处理孩子结点		levelVisit(root);    }};const int MAXSIZE = 1000;TreeLinkNode gNodeArr[MAXSIZE];int gIndex;TreeLinkNode* createNode(int value){	++gIndex;	gNodeArr[gIndex].val = value;	return &gNodeArr[gIndex];}//构建二叉树，这里默认首个元素为二叉树根节点，然后接下来按照作为每个结点的左右孩子的顺序遍历TreeLinkNode* buildBinaryTree(vector<int>& nums){	if(nums.empty())	{		return NULL;	}	TreeLinkNode* root;	int size = nums.size();	int j = 0;	//结点i的孩子结点是2i,2i+1	for(int i = 0 ; i < size ; i++)	{		if(i)		{			createNode(nums.at(i));		}		else		{			root = createNode(nums.at(i));		}	}	//设定孩子结点指向,	for(int i = 1 ; i <= size ; i++)	{		if(2 * i <= size)		{			gNodeArr[i].left = &gNodeArr[2*i];		}		if(2*i + 1 <= size)		{			gNodeArr[i].right = &gNodeArr[2*i + 1];		}	}	//设定完了之后，返回根节点	return root;}void process(){	 vector<int> nums;	 int value;	 int num;	 Solution solution;	 vector<string> result;	 while(cin >> num )	 {		 nums.clear();		 result.clear();		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 nums.push_back(value);		 }		 TreeLinkNode* root = buildBinaryTree(nums);		 solution.connect(root);	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}