Skip to content

108. 将有序数组转换为二叉搜索树 #79

Open
@Geekhyt

Description

@Geekhyt

原题链接

递归

  1. 二叉搜索树的中序遍历是升序的,本题中给出的数组刚好是升序的,相当于通过中序遍历恢复二叉搜索树
  2. 可以选择升序序列中的任意位置的元素作为根节点,该元素左边的升序序列构建左子树,右边的升序序列构建右子树
  3. 题目又要求高度平衡,所以我们需要选择升序序列的中间位置的元素作为根节点即可
const sortedArrayToBST = function (nums) {
    const buildTree = (Arr, left, right) => {
        if (left > right) return null

        let mid = Math.floor(left + (right - left) / 2)

        let root = new TreeNode(Arr[mid])
        root.left = buildTree(Arr, left, mid - 1)
        root.right = buildTree(Arr, mid + 1, right)
        return root
    }
    return buildTree(nums, 0, nums.length - 1)
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(logn)

Metadata

Metadata

Assignees

No one assigned

    Labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions