首页 > 代码库 > 108. Convert Sorted Array to Binary Search Tree

108. Convert Sorted Array to Binary Search Tree

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

 

给定有序数组构造二叉搜索树。考虑到二叉搜索树的性质(中序遍历二叉搜索树可以得到一个排序好的数组)

构造的过程如下 根结点的左孩子结点则选取根结点左边区域的中间数,右孩子结点同理

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

 

108. Convert Sorted Array to Binary Search Tree