首页 > 代码库 > Convert Sorted Array to Binary Search Tree
Convert Sorted Array to Binary Search Tree
https://oj.leetcode.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.
解题思路：
回忆一下BST二叉搜索树的定义，他是这样一个二叉树，他的顶节点比左节点大，比右节点小，同时他的左子树和右子树也是一个BST。这是一个递归的定义。
平衡BST的定义是，他是一个BST，同时他的左子树和右子树的高度差，不大于1。
构建平衡BST，就是选取当前数组的中间数字，作为当前节点，然后把左侧和右侧的数字分别放在左子树和右子树，然后对左子树和右子树做同样的动作。代码如下。
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */public class Solution { public TreeNode sortedArrayToBST(int[] num) { if(num.length == 0){ return null; } return toBST(num, 0, num.length - 1); } public static TreeNode toBST(int[] num, int start, int end){ int mid = (start + end) / 2; TreeNode treeNode = new TreeNode(num[mid]); if(start > end){ return null; } treeNode.left = toBST(num, start, mid - 1); treeNode.right = toBST(num, mid + 1, end); return treeNode; }}
和所有的递归算法一样，这里要注意递归的退出条件，即start > end。总结，这道题是看思路的一道题目，很简单，如果思路不清楚会想的很难，或者不能确定当前的解法是否正确。
Convert Sorted Array to Binary Search Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。