LeetCode精选TOP面试题108.将有序数组转换为二叉搜索树

题目描述

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
将有序数组转换为二叉搜索树的结果肯定是不唯一的，因为存在多种建树方法。

思路

思路一： 中序遍历–始终选择中间位置左边元素作为根节点；
思路二： 中序遍历–始终选择中间位置右边元素作为根节点；
思路三： 中序遍历–选择任意一个中间位置元素作为根节点。
以上三个思路借助的都是递归法+二叉树的中序遍历 ，中序遍历的定义就是访问结点的顺序为左->中->右

代码（Java实现）

import java.util.*;
public class Solution {
    int[] nums;
    public TreeNode Transfer(int left, int right) {
        if (left > right){
            // 退出递归的边界条件
            return null;
        }
        // 思路 1 ：始终选择中间位置左边元素作为根节点
        int midloc = (left + right) / 2;

        // 思路 2 ：始终选择中间位置右边元素作为根节点
        /*int midloc = (left + right) / 2;
        if ((left + right) % 2 == 1) {
            midloc ++;
        }*/

        // 思路 3 ：选择任意一个中间位置元素作为根节点
        /*int midloc = (left + right) / 2;
        Random rand = new Random();
        if ((left + right) % 2 == 1){
            midloc += rand.nextInt(2);
        }*/

        // 递归建树
        TreeNode root = new TreeNode(nums[midloc]);
        root.left = Transfer(left, midloc - 1);   // 左递归
        root.right = Transfer(midloc + 1, right);  // 右递归
        return root;
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        this.nums = nums;
        return Transfer(0, nums.length - 1);
    }
}

详解可参照LeetCode官方题解
完整的可运行代码请点击此处下载

本文作者： whtli
本文链接： https://hexo.whtli.cn/archives/cd1152fa.html
版权声明： 遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。