Convert Sorted Array to Binary Search Tree

题目介绍

LeetCode 108. Convert Sorted Array to Binary Search Tree，题目的意思将一个升序的数组转化为平衡二叉查找树。

balanced BST

二叉查找树（BST）是一种能够将链表插入的灵活性和有序数组查找的高效性结合起来的符号表实现。具体的说，就是使用每个节点含有两个链接（链表中每个节点只含有一个链接）的二叉查找树来高效地实现符号表。我们定义的数据结构由 结点 组成，结点包含的链接可以为空或者指向其他结点。在二叉树中，每个节点只能有一个父节点（只有一个例外，也就是根节点，它没有父节点），而且每个节点都只有左右两个链接，分别指向自己的左子节点和右子节点。二叉查找树的数据结构如下所示：

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

我们知道，对于一般的二叉搜索树，其期望高度（即为一棵平衡树时）为lgn，其各操作的时间复杂度 O(lgn) 同时也由此而决定，这样就和二分查找时间复杂度一致。但是，在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n)。我们在平时构造二叉搜索树的时候，会通过随机化建立二叉搜索树，来避免这种情况，但是这种距离平衡二叉搜索树的时间复杂度还是有一定的差距。平衡二叉搜索树（Balanced Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。不幸的是，在动态插入中保证树的完美平衡的代价太高了，相应的就有红黑二叉数等算法改进，这里不做过多介绍。

解题方法

因为是有序的数组，所以可以直接通过二分的方法来不断的进行递归插入。联想到二分方法的原因是，因为二分法的时间复杂度为 O(lgn)，而平衡二叉查找树的时间复杂度也为 O(lgn)。所以算法如下：

class Solution {
    func sortedArrayToBST(_ nums: [Int]) -> TreeNode? {
        if nums.isEmpty {
            return nil
        }

        return sortSubArrayToBST(nums, 0, nums.count - 1)
    }

    private func sortSubArrayToBST(_ nums: [Int], _ strat: Int, _ end: Int) -> TreeNode? {
        guard strat <= end else {
            return nil
        }

        let mid = (strat + end) / 2
        let node = TreeNode(nums[mid])
        node.left = sortSubArrayToBST(nums, strat, mid - 1)
        node.right = sortSubArrayToBST(nums, mid + 1, end)

        return node
    }
}

**版权声明**

Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。

本文首发于Ivan’s Blog | 叶帆的博客博客（ http://yeziahehe.com ），版权所有，侵权必究。

本文链接：http://yeziahehe.com/2017/11/02/ConvertSortedArrayToBinarySearchTree/