#include <iostream>#include <stdio.h>#include <vector>#include <queue>#include <sstream>using namespace std;/*問題:Given a binary tree    struct TreeLinkNode {      TreeLinkNode *left;      TreeLinkNode *right;      TreeLinkNode *next;    }Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.Initially, all next pointers are set to NULL.Note:You may only use constant extra space.You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).For example,Given the following perfect binary tree,         1       /  /      2    3     / /  / /    4  5  6  7After calling your function, the tree should look like:         1 -> NULL       /  /      2 -> 3 -> NULL     / /  / /    4->5->6->7 -> NULL分析:給定一顆二叉樹，填充結(jié)點的next指針來指向它的下一個右邊的結(jié)點。如果沒有下一個右側(cè)的結(jié)點，下一個指針應(yīng)該被設(shè)置為空。初始化，所有下一個指針都是被設(shè)置為NULL。注意：1】只能使用常量空間2】可以假設(shè)這顆二叉樹是一個完全二叉樹，所有的葉子結(jié)點都是在同一層每個父節(jié)點都有兩個孩子結(jié)點。根節(jié)點的next為空，從根節(jié)點往下，最左邊的孩子結(jié)點都會指向右邊的指針。假設(shè)當(dāng)前結(jié)點為root，root->left->next = root->right;root->right->next = NULL;這個類似之前做的判斷一棵樹是不是對稱，遞歸的輸入一定是當(dāng)前結(jié)點的左右孩子結(jié)點輸入:71 2 3 4 5 6 715-1 0 1 2 3 4 5 6 7 8 9 10 11 12 13輸出:1 NULL 2 3 NULL 4 5 6 7 NULL-1 NULL,0 1 NULL, 2 3 4 5 NULL, 6 7 8 9 10 11 12 13 NULL報錯:原因是中間有兩個結(jié)點忘記連接了Input:{-1,0,1,2,3,4,5,6,7,8,9,10,11,12,13}Output:{-1,#,0,1,#,2,3,4,5,#,6,7,8,9,#}Expected:{-1,#,0,1,#,2,3,4,5,#,6,7,8,9,10,11,12,13,#}						-1				0				1			2		3		4		5		  6	   7   8  9   10  11   12  13關(guān)鍵:1 這個類似之前做的判斷一棵樹是不是對稱，遞歸的輸入一定是當(dāng)前結(jié)點的左右孩子結(jié)點	//下面是左右孩子都非空的，讓左孩子的next指向右孩子，右孩子的next指向空	leftNode->next = rightNode;	rightNode->next = NULL;	//處理各自的左右孩子結(jié)點	connectHelper(leftNode->left , leftNode->right);	//別忘記中間需要連接,但是這一組卻不需要遞歸；也是需要遞歸的，否則會遺漏中間連接的部分，	connectHelper(leftNode->right , rightNode->left);	connectHelper(rightNode->left , rightNode->right);	}*/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:	//由于是完全二叉樹，那么一棵樹的左右孩子結(jié)點要么全部為空，要么全部都不空	void connectHelper(TreeLinkNode* leftNode , TreeLinkNode* rightNode )	{		//當(dāng)前結(jié)點的孩子結(jié)點都為空，無需連接		if(NULL == leftNode && NULL == rightNode)		{			return;		}		//只有一個為空，不符合題目條件，不處理		if(NULL == leftNode || NULL == rightNode)		{			return;		}		//下面是左右孩子都非空的，讓左孩子的next指向右孩子，右孩子的next指向空		leftNode->next = rightNode;		rightNode->next = NULL;		//處理各自的左右孩子結(jié)點		connectHelper(leftNode->left , leftNode->right);		//別忘記中間需要連接,但是這一組卻不需要遞歸；也是需要遞歸的，否則會遺漏中間連接的部分，		connectHelper(leftNode->right , rightNode->left);		connectHelper(rightNode->left , rightNode->right);	}    void connect(TreeLinkNode *root) {		//根節(jié)點為空，不需要處理        if(!root)		{			return;		}		//接下來設(shè)置根節(jié)點自己的next指針為null		root->next = NULL;		//遞歸處理孩子結(jié)點		connectHelper(root->left , root->right );    }};const int MAXSIZE = 1000;TreeLinkNode gNodeArr[MAXSIZE];int gIndex;TreeLinkNode* createNode(int value){	++gIndex;	gNodeArr[gIndex].val = value;	return &gNodeArr[gIndex];}//構(gòu)建二叉樹，這里默認(rèn)首個元素為二叉樹根節(jié)點，然后接下來按照作為每個結(jié)點的左右孩子的順序遍歷TreeLinkNode* buildBinaryTree(vector<int>& nums){	if(nums.empty())	{		return NULL;	}	TreeLinkNode* root;	int size = nums.size();	int j = 0;	//結(jié)點i的孩子結(jié)點是2i,2i+1	for(int i = 0 ; i < size ; i++)	{		if(i)		{			createNode(nums.at(i));		}		else		{			root = createNode(nums.at(i));		}	}	//設(shè)定孩子結(jié)點指向,	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];		}	}	//設(shè)定完了之后，返回根節(jié)點	return root;}//層序遍歷void levelVisit(TreeLinkNode* root, vector< string >& result){	if(!root)	{		return;	}	queue<TreeLinkNode*> nodes;	nodes.push(root);	int size = 1;	int nextSize = 0;	TreeLinkNode* node;	vector<TreeLinkNode*> beginNodes;	//先找到每一層的起始結(jié)點，也就是size=0的結(jié)點，然后對每個起始結(jié)點遍歷即可	while(!nodes.empty())	{		node = nodes.front();		nodes.pop();				//將每一層的起始結(jié)點存儲起來		if(0 == nextSize)		{			beginNodes.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;		}	}	if(beginNodes.empty())	{		return;	}	int len = beginNodes.size();	TreeLinkNode* head = NULL;	for(int i = 0 ; i < len ; i++)	{		head = beginNodes.at(i);		stringstream stream;		while(head)		{			stream << head->val << "->";			head = head->next;		}		stream << "NULL";		result.push_back(stream.str());	}}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;}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);		 levelVisit(root, result);		 print(result);	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}