#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;}