leetcode 刷题之路 14 Convert Sorted Array to Binary Search Tree

本文主要是介绍leetcode 刷题之路 14 Convert Sorted Array to Binary Search Tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

题目要求将有序数组转换为一个二元查找树。树的题目大部分都可以采用递归来解决，这道题也不例外。一个二元查找树的左子树上的所有节点都小于根节点，右子树上的所有节点都大于根节点，同时二元查找树左子树和右子树上高度尽量接近，能够保证进行查询，插入，删除等操作的时间复杂度接近于O(logn)，因此，我们以数组最中间的元素为根节点值，可以使得二元查找树达到平衡状态，然后再用数组的左半边元素和右半边元素分别来递归的建立该根节点的左右子树。

通过上面的讲解，不难写出下面的程序：

my accepted answer:

/*** 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){helper(num, 0, num.size() - 1);}static TreeNode* helper(vector<int> &num, int begin, int end){if (begin > end)return NULL;if (begin == end)return new TreeNode(num[begin]);int mid = (begin + end) / 2;TreeNode *tn = new TreeNode(num[mid]);tn->left = helper(num, begin, mid - 1);tn->right = helper(num, mid + 1, end);return tn;}
};

这篇关于leetcode 刷题之路 14 Convert Sorted Array to Binary Search Tree的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---