《Cracking the Coding Interview》——第4章：树和图—

《Cracking the Coding Interview》——第4章：树和图——题目3

2014-03-19 03:34

题目：给定一个排好序的数组，设计算法将其转换为一棵二叉搜索树，要求树的高度最小。

解法：递归生成平衡二叉树，使左右子树的节点数尽量相等，所以对半开最好了。其实也可以生成一棵完全二叉树，不过写法应该不是很方便。

代码：

 1 // 4.3 Convert sorted unique array to height-balanced binary search tree.
 2 #include <cstdio>
 3 using namespace std;
 4 
 5 struct TreeNode {
 6     int val;
 7     TreeNode *left;
 8     TreeNode *right;
 9     
10     TreeNode(int _val = 0): val(_val), left(nullptr), right(nullptr) {};
11 };
12 
13 void consructBSTFromSortedArray(vector<int> &v, int left, int right, TreeNode *&root)
14 {
15     if (left > right) {
16         root = nullptr;
17     } else {
18         int mid = (left + right + 1) / 2;
19         root = new TreeNode(v[mid]);
20         consructBSTFromSortedArray(v, left, mid - 1, root->left);
21         consructBSTFromSortedArray(v, mid + 1, right, root->right);
22     }
23 }
24 
25 void preorderTraversal(TreeNode *root)
26 {
27     if (root == nullptr) {
28         printf("# ");
29     } else {
30         printf("%d ", root->val);
31         preorderTraversal(root->left);
32         preorderTraversal(root->right);
33     }
34 }
35 
36 void clearBinaryTree(TreeNode *&root)
37 {
38     if (root == nullptr) {
39         return;
40     } else {
41         clearBinaryTree(root->left);
42         clearBinaryTree(root->right);
43         delete root;
44         root = nullptr;
45     }
46 }
47 
48 int main()
49 {
50     TreeNode *root;
51     int i, n;
52     vector<int> v;
53     
54     while (scanf("%d", &n) == 1 && n > 0) {
55         for (i = 0; i < n; ++i) {
56             v.push_back(i + 1);
57         }
58         
59         consructBSTFromSortedArray(v, 0, n - 1, root);
60         preorderTraversal(root);
61         printf("
");
62         
63         v.clear();
64         clearBinaryTree(root);
65     }
66     
67     return 0;
68 }