题目描述

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);
    }
};