文章
问答
冒泡
将有序数组转换为一颗高度平衡的二叉搜索树

二叉搜索树

二叉搜索树可以是一颗空树或者具备如下特性的一棵树:

  1. 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值
  2. 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值
  3. 任意节点的左、右子树也分别为二叉搜索树
  4. 没有键值相等的节点
  5. 一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。


前置条件

给定一个数组,但此数组是有序的。


解决思路

通过结合二叉搜索树的特性可以得知,二叉搜索树通过 中序遍历之后得到的是一个有序数组。

中序输出的过程为:左节点 -> 根节点 -> 右节点


此时发现其实这是一个逆向过程,根据已有的排序数组逆向构造二叉树。


那么我们如何保证高度平衡呢?


很简单,我们是否想到了二分法?通过二分法找到根节点,然后再在二分好数组的基础上重复性的执行。


想到了重复,我们根据自己的经验学习,第一反应出现的应该是递归和迭代。此种情况我们采用递归。


递归处理过程中,除了分析出递归公式之外,还要分析分析递归条件。


此场景的递归条件即为 startIndex 和 endIndex 的比较,当子数组的 startIndex > endIndex 的时候即退出递归逻辑。


具体实现

public TreeNode sortedArrayToBST(int[] nums) {
    /** --- 边界条件处理 ---- **/
    if( nums == null || nums.length == 0) {
        return null;
    }
    int startIndex = 0, endIndex = nums.length - 1;

    /** ---
    TreeNode treeNode = createTree(nums, startIndex, endIndex);
    return treeNode;
}

private TreeNode createTree(int[] nums, int start, int end) {
    /** --- 递归条件 --- **/
    if(start > end) {
        return null;
    }

    /** --- 此处 mid 计算是要保证 startIndex 存在一个基准值 ---- **/
    int mid = start + (end-start) / 2;
    TreeNode root = new TreeNode(nums[mid]);

   /** --- startIndex 及 endIndex 不能通过事先变量定义,因为在处理递归过程中
   **  退出递归之后能够找回之前的 startIndex 及 endIndex 值,所以在参数中通过
   **  变量运算来传参保证能够找回递归之前的值
   **/
    root.left = createTree(nums, start, mid -1 );
    root.right = createTree(nums, mid + 1, end);


    return root;
}

知识点: 平衡二叉搜索树、递归、二分法、中序遍历



github代码链接

平衡二叉搜索树
递归
二分法

关于作者

Kirago
个人站点 https://kiragoo.github.io/
获得点赞
文章被阅读