LeetCode 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.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

给定一个升序排列的数组,要构建一个高度平衡的二叉搜索树。 二叉搜索树的概念是递归定义的,具体可以参看维基百科,简单来说就是左孩子小于根节点,右孩子大于根节点。 但是本题要求二叉搜索树是高度平衡的,也就是说左右孩子的高度差不能大于1。 我一开始的想法是既然是平衡二叉搜索树,直接取数组中点,然后左右依次排开,肯定能得到一棵平衡二叉搜索树,如下左图所示。 但是这一版本的代码提交上去之后只通过了6个样例。后来仔细想了想,这解法未免也太简单幼稚了吧。想到之前解树的题都用到了递归,这题应该也可以用,立马灵光一闪,第一次取中点之后,递归的在左右半个数组中取中点建树,所有还可以得到如上右图所示的更加紧凑的平衡二叉搜索树。

完整代码如下:

class Solution {
public:
    TreeNode* work(vector<int>& nums, int s, int t)
    {
        if (s == t)
            return new TreeNode(nums[s]);
        if (s > t)
            return NULL;
        int mid = (s + t + 1) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = work(nums, s, mid – 1);
        root->right = work(nums, mid + 1, t);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) { return work(nums, 0, nums.size() – 1); }
};

本代码提交AC,用时16MS。

1 thought on “LeetCode Convert Sorted Array to Binary Search Tree

  1. Pingback: LeetCode Convert Sorted List to Binary Search Tree | bitJoy > code

Leave a Reply

Your email address will not be published. Required fields are marked *