leetcode/108. Convert Sorted Array to Binary Search Tree.cpp at master · yunfengzhou-hub/leetcode · GitHub

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
/**
 * 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) {
        int middle,start,finish;
        TreeNode* result,*temp;
        queue<TreeNode*> nodes;
        queue<pair<int,int>> ranges;

        if(nums.size()<1) return NULL;

        result=new TreeNode(0);
        nodes.push(result);
        ranges.push(make_pair(0,nums.size()));
        while(nodes.size()>0){
            start=ranges.front().first;
            finish=ranges.front().second;
            temp=nodes.front();

            middle=(start+finish)/2;
            temp->val=nums[middle];

            if(middle-start>0){
                temp->left=new TreeNode(0);
                nodes.push(temp->left);
                ranges.push(make_pair(start,middle));
            }
            if(finish-middle>1){
                temp->right=new TreeNode(0);
                nodes.push(temp->right);
                ranges.push(make_pair(middle+1,finish));
            }

            nodes.pop();
            ranges.pop();
        }

        return result;
    }
};