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

Convert Sorted Array to Binary Search Tree leetcode java

题目

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

 

题解

先复习下什么是二叉搜索树(引自Wikipedia):

二叉查找树Binary Search Tree),也称有序二叉树(ordered binary tree),排序二叉树(sorted binary tree),是指一棵空树或者具有下列性质的二叉树:

  1. 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  2. 任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
  3. 任意节点的左、右子树也分别为二叉查找树。

 

 

再复习下什么是平衡二叉树(引自GeekforGeek):

An empty tree is height-balanced. A non-empty binary tree T is balanced if:
  1) Left subtree of T is balanced
  2) Right subtree of T is balanced
  3) The difference between heights of left subtree and right subtree is not more than 1. 

 

解决方法是选中点构造根节点,然后递归的构造左子树和右子树。

代码如下:

 1     public TreeNode buildTree(int[] num, int low, int high){
 2         if(low>high)
 3             return null;
 4         
 5         int mid = (low+high)/2;
 6         TreeNode node = new TreeNode(num[mid]);
 7         node.left = buildTree(num,low,mid-1);
 8         node.right = buildTree(num,mid+1,high);
 9         return node;
10     }
11     public TreeNode sortedArrayToBST(int[] num) {
12        return buildTree(num,0,num.length-1);
13     }