LeetCode108—Convert Sorted Array to Binary Search Tree

建構排序二叉樹。

原題

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

給定一個遞增序列，通過此序列建構一個平衡排序二叉樹BST。

分析

一開始沒注意

height balanced

關鍵字，想着直接疊代BST插入走你，這樣肯定建立的二叉樹是“一路向右”。此題的正确姿勢是：由于BST的中序周遊是遞增的，那麼生成序列的中點為根，左邊節點為左子樹，右邊節點為右子樹，根據此，找到中點後，對左子樹和右子樹分别遞歸找到左子樹和右子樹。。

代碼

class Solution {
private:
    TreeNode* helper(vector<int>&nums, int left, int right)
    {
        if (left > right)
        {
            return NULL;
        }
        int mid = left + (right - left) / ;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = helper(nums, left, mid - );
        root->right = helper(nums, mid + , right);
        return root;
    }
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode*root = helper(nums, , nums.size() - );
        return root;
    }
};