LeetCode 108. Convert Sorted Array to Binary Search Tree(有序数组转二叉搜索树)
题目描述
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);
}
};