首页 > 代码库 > Convert Sorted Array to Binary Search Tree
Convert Sorted Array to Binary Search Tree
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/#/description
把升序数组转成一个height平衡二叉树。这个平衡两个字一开始吓到我了，后面发现用最直觉的方法转换的话，高度是保证平衡的，也就是说左树和右树的高度差不会大于1。
方法就是，找到数组的中位数，然后以此把数组剖两半，分别做左右子树。这样递归的下去直到数组为空。
可以保证高度平衡是因为，把一个数组剖两半有两种情况：1. 数组是奇数，这样左右树高度会完全一致。2. 数组是偶数，那么左右树的节点数量只会相差1，这样高度也只会相差1.故平衡。
//Definition for a binary tree node.function TreeNode(val) { this.val = val; this.left = this.right = null;}var sortedArrayToBST = function(nums) { return ct(nums, 0, nums.length-1);};function ct(arr, left, right) { if (left > right) return null; var mid = parseInt((left + right) / 2); var root = new TreeNode(arr[mid]); root.left = ct(arr, left, mid - 1); root.right = ct(arr, mid + 1, right); return root;}
Convert Sorted Array to Binary Search Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。