510，将有序数组转换为二叉搜索树

Original 山大王wld 数据结构和算法 2022-05-09

收录于合集 #算法图文分析 161个

Opportunity does not knock, it presents itself when you beat down the door.

机遇不会自己找上门来，它只会在你开门时出现。

问题描述

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

示例:

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

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

0 / \ -3 9 / / -10 5

递归方式解决

题中说了要转换为一棵高度平衡的二叉搜索树，并且数组又是排过序的，这就好办了。

我们可以使用递归的方式，每次取数组中间的值比如m作为当前节点，m前面的值都是比他小的，作为他左子树的结点值。m后面的值都是比他大的，作为他右子树的节点值，示例中一个可能的结果是。

代码如下

 1public TreeNode sortedArrayToBST(int[] num) {
 2    //边界条件判断
 3    if (num.length == 0)
 4        return null;
 5    return sortedArrayToBST(num, 0, num.length - 1);
 6}
 7
 8//start表示数组开始的位置，end表示的结束的位置
 9public TreeNode sortedArrayToBST(int[] num, int start, int end) {
10    if (start > end)
11        return null;
12    int mid = (start + end) >> 1;
13    //取中间值作为当前节点
14    TreeNode root = new TreeNode(num[mid]);
15    //然后递归的方式，中间值之前的是当前节点左子树的所有节点
16    root.left = sortedArrayToBST(num, start, mid - 1);
17    //中间值之后的是当前节点的右子树的所有节点
18    root.right = sortedArrayToBST(num, mid + 1, end);
19    return root;
20}