将有序数组转化为二叉搜索树

发表于
本文字数： 1k 阅读时长 ≈ 1 分钟

LeetCode每日一题，108.Convert Sorted Array to Binary Search Tree

先看题目描述

大意是根据给定的升序数组，恢复一棵高度平衡的二叉搜索树

算法和思路

二叉搜索树的中序遍历是升序的，因此本题等同于根据中序遍历的序列恢复二叉搜索树。因此我们可以以升序序列中的任一个元素作为根节点，以该元素左边的升序序列构建左子树，以该元素右边的升序序列构建右子树，这样得到的树就是一棵二叉搜索树， 又因为本题要求高度平衡，因此我们需要每次选择升序序列的中间元素来作为根节点(个人感觉有点类似于二分法，二分法在算法题中真的很常用)

注意：给定二叉搜索树的中序遍历，又要求二叉搜索树的高度是平衡的，是否可以唯一地确定二叉搜索树？答案是否定的。故可能的二叉搜索树有多个

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return findRoot(nums, 0, nums.length - 1);;
    }

    public TreeNode findRoot(int[] nums, int left, int right) {
        if (left > right) return null;
        int mid = (left + right) / 2;
        TreeNode root = new TreeNode(mid);
        root.left = findRoot(nums, left, mid - 1);
        root.right = findRoot(nums, mid + 1, right);
        return root;
    }
}