题目描述

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, 2, 3, 4, 5, 6, 7]，根节点的值就是4，此时左半数组是[1, 2, 3]，那么根结点的左子节点的值就是2，依此类推，我们就能建立如下的二叉搜索树：

     4
   /   \
  2     6
 / \   / \
1   3 5   7

注意刚才说“重叠子问题”，那么我们就可以用递归来解决，即，对于一个数组，取出中间元素值作为当前根结点，而根结点的左子树就是“以左半数组为输入的递归”，根节点的右子树就是“以右半数组为输入的递归”，对于当前递归返回当前根结点。

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution:
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        def to_bst(nums, start, end):
            if start > end:
                return None
            mid = (start + end) // 2
            node = TreeNode(nums[mid])
            node.left = to_bst(nums, start, mid - 1)
            node.right = to_bst(nums, mid + 1, end)
            return node

        return to_bst(nums, 0, len(nums) - 1)

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        class Utils {
            TreeNode toBST(int[] nums, int start, int end) {
                if (start > end) {
                    return null;
                }
                int mid = (start + end) / 2;
                TreeNode node = new TreeNode(nums[mid]);
                node.left = toBST(nums, start, mid - 1);
                node.right = toBST(nums, mid + 1, end);
                return node;
            }
        }
        Utils utils = new Utils();
        return utils.toBST(nums, 0, nums.length - 1);
    }
}

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *sortedArrayToBST(vector<int> &nums) {
        class Utils {
        public:
            TreeNode *toBST(vector<int> &nums, int start, int end) {
                if (start > end) {
                    return nullptr;
                }
                int mid = (start + end) / 2;
                TreeNode *node = new TreeNode(nums[mid]);
                node->left = toBST(nums, start, mid - 1);
                node->right = toBST(nums, mid + 1, end);
                return node;
            }
        };
        Utils utils;
        return utils.toBST(nums, 0, nums.size() - 1);
    }
};