首页 > 代码库 > Convert Sorted Array to Binary Search Tree

Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

将增序数组转换为左右均衡的二叉查找树 根据查找树的性质 左子树所有节点小于根节点值 右边都大于根节点值 子树也遵循此性质 所以只要取出增序数组的中间值作为根节点 再将左右子数组进行递归 代码如下:

public class Solution {
    public TreeNode sortedArrayToBST(int[] num) {
        if(num.length==0)return null;
		TreeNode root=new TreeNode(num[num.length/2]);
		int[] leftnum=new int[num.length/2];
		for(int i=0;i<num.length/2;i++){
			leftnum[i]=num[i];
		}
		root.left=sortedArrayToBST(leftnum);
		int[] rightnum=new int[num.length-num.length/2-1];
		for(int i=0;i<num.length-num.length/2-1;i++){
			rightnum[i]=num[num.length/2+i+1];
		}
		root.right=sortedArrayToBST(rightnum);
		return root;
    }
}


Convert Sorted Array to Binary Search Tree