首页 > 代码库 > 【LeetCode】Convert Sorted Array to Binary Search Tree

【LeetCode】Convert Sorted Array to Binary Search Tree

Convert Sorted Array to Binary Search Tree

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

 

这题思路参照Convert Sorted List to Binary Search Tree,由于vector可以用下标访问,因此不用设置快慢节点,直接访问中间点。

/** * Definition for binary tree * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    TreeNode *sortedArrayToBST(vector<int> &num) {        if(num.empty())            return NULL;        else            return Helper(num, 0, num.size()-1);    }    TreeNode *Helper(vector<int> &num, int begin, int end)    {        if(begin > end)            return NULL;        else        {            int mid = (begin+end)/2;            int midV = num[mid];            TreeNode* root = new TreeNode(midV);            root->left = Helper(num, begin, mid-1);            root->right = Helper(num, mid+1, end);            return root;        }    }};

【LeetCode】Convert Sorted Array to Binary Search Tree