使用层次遍历重建二叉树并遍历

58同城的一道题，蛮有意思的。利用层次遍历后的数组，进行二叉树的重建。数值-1代表NULL。

解题思路：那么我们依然使用队列，进行层次遍历，进行重建，这边有的问题是当示例为array[] = { 1, 2, 3, 4, -1, 5, 6, 7, 8, -1, -1, 9, 10 , -1, -1 }时，那么需要注意去除NULL，因为NULL节点下面两个节点必然为NULL。

参考代码：

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <set>

using namespace std;

class Solution {
public:
	/**
	* 对给定的二叉树依次完成前序，中序，后序遍历，并输出遍历结果
	* @param input int整型一维数组 -1表示Nil节点
	* @param inputLen int input数组长度
	* @return int整型vector<vector<>>
	*/
	struct tree_node{
		int val;
		tree_node* left;
		tree_node* right;
		tree_node(int x) :val(x), left(NULL), right(NULL){}
	};

	vector<vector<int> > binaryTreeScan(int* input, int inputLen) {
		// write code here
		vector<vector<int> > res;
		if (inputLen <= 0)
			return res;

		tree_node* root = creat_node(input, inputLen);
		vector<int> front_data;
		vector<int> mid_data;
		vector<int> back_data;

		front(root, front_data);
		mid(root, mid_data);
		back(root, back_data);

		res.push_back(front_data);
		res.push_back(mid_data);
		res.push_back(back_data);

		return res;
	}

	tree_node* creat_node(int* input, int inputLen)
	{
		if (inputLen <= 0)
			return NULL;

		queue<tree_node*> my_q;
		tree_node* new_node = new tree_node(input[0]);
		my_q.push(new_node);

		tree_node* bt;
		int i = 1;
		while (!my_q.empty())
		{
			bt = my_q.front();
			my_q.pop();
            //将NULL作为标志，既然为空，那么对应的左右子树必然为NULL，数组中必然为-1，所以直接过滤
			if (bt == NULL)
			{
				i += 2;
				continue;
			}

			if (i < inputLen)
			{
				if (input[i] != -1)
				{
					bt->left = new tree_node(input[i]);
					my_q.push(bt->left);
				}
				else{
					bt->left = NULL;
					my_q.push(NULL);
				}
				i++;
			}
			else{
				bt->left = NULL;
			}

			if (i < inputLen)
			{
				if (input[i] != -1)
				{
					bt->right = new tree_node(input[i]);
					my_q.push(bt->right);
				}
				else{
					bt->right = NULL;
					my_q.push(NULL);
				}
				i++;
			}
			else{
				bt->right = NULL;
			}
		}
		return new_node;
	}

	void front(tree_node* root, vector<int>& front_data)
	{
		if (root == NULL)
			return;

		front_data.push_back(root->val);
		front(root->left, front_data);
		front(root->right, front_data);
	}

	void mid(tree_node* root, vector<int>& mid_data)
	{
		if (root == NULL)
			return;

		mid(root->left, mid_data);
		mid_data.push_back(root->val);
		mid(root->right, mid_data);
	}

	void back(tree_node* root, vector<int>& back_data)
	{
		if (root == NULL)
			return;

		back(root->left, back_data);
		back(root->right, back_data);
		back_data.push_back(root->val);
	}
};

int main()
{
	Solution solution;

	int array[] = { 1, 2, 3, 4, -1, 5, 6, 7, 8, -1, -1, 9, 10 , -1, -1 };
	
	int arrayLen = 15;
	solution.binaryTreeScan(array,arrayLen);

	system("pause");
	return 0;
}