LeetCode筆記：Convert Sorted Array to Binary Search Tree

一. 題目描述

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

二. 題目分析

將二叉查找樹進行中序遍歷，就可以得到一個升序排序的數組，因此，一個已經排序的數組可以看做一個中序遍歷得到的數組，要得到一個高度平衡的二叉查找樹，可以使得左右子樹的節點數盡可能相等。因此，可以采用二分法將數組分為兩個子數組，中間值作為父節點，左邊的子數組作為左子樹，右邊的子數組作為右子樹進行遞歸，這樣就可以得到一個高度平衡的二叉查找樹。

三. 示例代碼

#include 
#include 

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


class Solution
{
public:
    TreeNode* sortedArrayToBST(vector& nums)
    {
        return generateBST(0, num.size() - 1, num);
    }

private:
    TreeNode* generateBST(int left, int right, vector& num)  
    {  
        if (left > right)  
            return nullptr;  
        else if (left == right)  
            return new TreeNode(num[left]);  
        else  
        {  
            int mid = (left + right) / 2;  
            TreeNode* node = new TreeNode(num[mid]);  
            node->left = generateBST(left, mid - 1, num);  
            node->right = generateBST(mid + 1, right, num);  
            return node;  
        }  
    }  
};

四. 小結

這道題的技巧主要在於二叉查找樹的中序遍歷就是一個升序的數組，因此，本題就是根據一個二叉查找樹的中序構建一個二叉查找樹，由於要求高度平衡，因此，可以考慮左右兩個子樹的結點個數相同，這樣就可以得到唯一的一顆二叉查找樹。