Author: qyh

Date: 2019-03-14

Description: Buid BT Stree from preorder tree

URL:https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

/*Definition for a binary tree node.*/
struct TreeNode {
	int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
 
class Solution {
public:
	/***********************
	求解思路：
	其实很简单，就是简单的二叉搜索树的插入，然后输出根节点就行了，没有那么复杂。。。
	***********************/

	TreeNode* bstFromPreorder(vector<int>& preorder) {
		if (preorder.empty())
			return NULL;
		TreeNode* root = new TreeNode(preorder[0]);
		for (int i = 1; i < preorder.size(); i++){
			insert(root, preorder[i]);
		}
		return root;
	}

	TreeNode* insert(TreeNode* &root, int val) {
		if (root == NULL)
			root = new TreeNode(val);
		else if (root->val > val) {
			root->left = insert(root->left, val);
		}
		else {
			root->right = insert(root->right, val);
		}
		return root;
	}

};


void levelOrder(TreeNode* root) {
	if (root == NULL) return;
	queue<TreeNode*> Q;
	Q.push(root);
	while (!Q.empty()) {
		TreeNode* tmp = Q.front();
		cout << tmp->val << endl;
		Q.pop();
		if (tmp->left != NULL) {
			Q.push(tmp->left);
		}
		if (tmp->right != NULL) {
			Q.push(tmp->right);
		}
	}
}


int main() {
	vector<int> test;
	int val[6] = {8, 5, 1, 7, 10, 12};
	for (int i = 0; i < 6; i++) {
		test.push_back(val[i]);
	}
	Solution sol;
	TreeNode* root = sol.bstFromPreorder(test);
	levelOrder(root);
	system("pause");
}