leetcode_convert_sorted_array_to_binary_tree

发表于

难度：Medium

解题思路：数组的中间当根节点，然后从左边区间的中间找左节点，从右边区间的中间找右节点。如此往复。
代码如下：

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
/**
 * 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* sortedArrayToBST(vector<int>& nums) {
        TreeNode* tn = find_left_right(nums, 0, nums.size()-1);
        return tn;
    }
    TreeNode* find_left_right(vector<int>& nums, int first, int second)
    {
        if(first > second) 
        {
            std::cout<<"first > second"<<std::endl;
            return nullptr;
        }
        else if(first == second)
        {
            std::cout<<"first == second"<<std::endl;
            TreeNode* t = new TreeNode(nums[first]);
            return t;
        }
        else
        {
            int mid = (first+second)/2;
            std::cout<<"mid:"<<mid<<std::endl;
            TreeNode* t = new TreeNode(nums[mid]);
            t->left = find_left_right(nums, first ,mid-1);
            t->right = find_left_right(nums, mid+1, second);
            std::cout<<"final"<<t->val<<std::endl;
            return t;
        }
    }   
};

运行结果：69ms，超过4.13%