二叉树测试用例-前序遍历

#include<vector>
#include<stack>

using namespace std;

struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};



TreeNode* buildtree(vector<int> array, int index)
{
	TreeNode* root = nullptr;

	if (index < array.size() && array[index] != NULL)
	{
		root = new TreeNode(array[index]);
		root->left = buildtree(array, 2 * index + 1);
		root->right = buildtree(array, 2 * index + 2);
	}
	return root;
}

vector<int> preorder(TreeNode* root) {
	vector<int> res;
	TreeNode* p = root;
	stack<TreeNode*> s;
	while (p || !s.empty()) {
		if (p) {
			s.push(p);
			res.push_back(p->val);
			p = p->left;
		}
		else {
			p = s.top();
			s.pop();
			p = p->right;
		}
	}
	return res;
}



int main()
{
	vector<int> array = { 4,1,6,9,2,5,7,NULL,NULL,NULL,3,NULL,NULL,NULL,8 };
	TreeNode* root;
	root = buildtree(array, 0);

	vector<int> final = preorder(root);
	for (int i = 0; i < final.size(); i++) {
		cout << final[i] << " ";
	}
	return 0;
}