当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.108.Convert Sorted Array to Binary Search Tree 升序数组转BST

LeetCode.108.Convert Sorted Array to Binary Search Tree 升序数组转BST

题目描述

108 Convert Sorted Array to Binary Search Tree
https://leetcode-cn.com/problems/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

解题过程

二叉搜索树 BST 的中序遍历序列就是升序数组
给定 bst 的中序遍历序列,生成的 bst 是不一定的,最极端的,可以生成一个高度为 n 的单边二叉树。
为了尽可能的使 bst 平衡,可以每次取中间节点作为根,然后递归的生成左右子树。

时间复杂度 O(n),空间复杂度 O(logn)

SolutionV202001

private static class SolutionV202001 {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (null == nums) {
            return null;
        }
        return sortedArrayToBSTRecursive(nums, 0, nums.length -1 );
    }

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

SolutionV202007

和半年前写的代码竟然一模一样。

private static class SolutionV202007 {
    public TreeNode sortedArrayToBST(int[] nums) {
        return toBST(nums, 0, nums.length - 1);
    }

    // 递归的将 nums[left...right] 转换为 bst
    private TreeNode toBST(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }
        if (left == right) {
            return new TreeNode(nums[left]);
        }
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = toBST(nums, left, mid - 1);
        root.right = toBST(nums, mid + 1, right);
        return root;
    }
}

GitHub代码

algorithms/leetcode/leetcode/_108_ConvertSortedArrayToBinarySearchTree.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_108_ConvertSortedArrayToBinarySearchTree.java


上一篇 LeetCode.110.Balanced Binary Tree 是否平衡二叉树

下一篇 LeetCode.107.Binary Tree Level Order Traversal II 二叉树自底向上层次遍历

阅读
评论
395
阅读预计2分钟
创建日期 2020-01-21
修改日期 2020-07-03
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论