leetcode

题目：Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

个人思路：

1、选取数组的中点作为根节点，中点左半边的数作为根节点的左子树节点，右半边的数作为根节点的右子树节点，递归地对左子树和右子树进行处理

2、递归结束条件为数组的起始点大于结束点

代码：

 1 #include <stddef.h>
 2 #include <vector>
 3 #include <iostream>
 4 
 5 using namespace std;
 6 
 7 struct TreeNode
 8 {
 9     int val;
10     TreeNode *left;
11     TreeNode *right;
12     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
13 };
14 
15 class Solution
16 {
17 public:
18     TreeNode *sortedArrayToBST(vector<int> &num)
19     {
20         TreeNode *root = build(num, 0, num.size() - 1);
21         //cout << root->val << endl;
22         //preorder(root);
23         return root;
24     }
25     void preorder(TreeNode *root)
26     {
27         if (root == NULL)
28         {
29             return;
30         }
31         cout << root->val << endl;
32         preorder(root->left);
33         preorder(root->right);
34     }
35 private:
36     TreeNode *build(vector<int> &num, int start, int end)
37     {
38         if (start > end)
39         {
40             return NULL;
41         }
42 
43         int middle = (start + end) / 2;
44         TreeNode *treeNode = new TreeNode(num[middle]);
45         treeNode->left = build(num, start, middle - 1);
46         treeNode->right = build(num, middle + 1, end);
47 
48         //cout << treeNode->val << endl;
49 
50         return treeNode;
51     }
52 };
53 
54 int main()
55 {
56     Solution s;
57     vector<int> v;
58     v.push_back(1);
59     v.push_back(2);
60     v.push_back(3);
61     v.push_back(4);
62     v.push_back(5);
63     v.push_back(6);
64 
65     TreeNode *root = s.sortedArrayToBST(v);
66     s.preorder(root);
67 
68     system("pause");
69     return 0;
70 }

View Code

网上的方法都是类似的