面试题 04.02. 最小高度树

题目介绍

描述：

给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。

示例:
给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

          0 
         / \\ 
       -3   9 
       /   / 
     -10  5

解题思路：

递归算法的关键是要明确函数的「定义」是什么，然后相信这个定义，利用这个定义推导最终结果。

写树相关的算法，简单说就是，先搞清楚当前 root 节点该做什么，然后根据函数定义递归调用子节点，递归调用会让孩子节点做相同的事情。

二叉树题目的一个难点在于如何通过题目的要求思考出每一个节点需要做什么

先看定义:

二叉搜索树（Binary Search Tree）

它或者是一棵空树，或者是具有下列性质的二叉树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉搜索树。

解题策略

一递归二队列 + 迭代（层次遍历）三栈 + 迭代（非递归遍历）四其它

三种基本的遍历方式，都可以用递归来实现。写递归算法的时候，需要注意递归退出条件以及递归操作的表达。

自己的解法实现

def sortedArrayToBST(self, nums):
        if not nums: return None
        low, high = 0, len((nums)) - 1
        mid = (low + high)//2
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid + 1 :])

        return root

网上比较优秀的解法

解法一

递归构建要求高度最小，保持高度平衡，也就是说左右子树的节点个数应该尽可能接近，那么我们可以如此进行：

用nums数组的中间值mid作为根节点，根据mid划分左子数组和右子数组。左子数组构建左子树，右子数组构建右子树。
那么现在的问题就转化为怎么用左子数组构建左子树/右子数组构建右子树，以左子数组构建左子树为例；
为了保持高度平衡，继续采用（1）中的划分方法，划分出新的左子数组和右子数组；
当左子数组/右子数组为空时，返回null。
右子数组构建右子树的过程与上述相同。

def sortedArrayToBST2(self, nums):
        def helper(nums, low, high):
            if low > high: return None
            mid = (high + low)//2
            root = TreeNode(nums[mid])
            # 左子数组[low, mid -1]构建左子树
            root.left = helper(nums, low, mid)
            # 右子数组[mid + 1, high]构建右子树
            root.right = helper(nums, mid + 1, high)
            return root
        return helper(nums, 0, len(nums) - 1)

解法二

通过二叉搜索树的定义，我们可以知道其根节点必然是有序整数序列的中位数，对于长度为奇数的序列来说，很自然地取到中位数，对于长度为偶数的序列，根节点取右中位数。由于是有序整数，那么在找到根节点后，我们可以将数组一分为二，其左侧必然是左子树，右侧必然是右子树。最后再考虑一下终止条件，就是这样一直划分到数组为空。

def sortedArrayToBST3(self, nums):
        if not nums: return
        mid = len(nums)//2
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums[: mid])
        root.right = self.sortedArrayToBST(nums[mid + 1:])

        return root