首页 > 代码库 > 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),是指一棵空树或者具有下列性质的二叉树:
- 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
- 任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
- 任意节点的左、右子树也分别为二叉查找树。
再复习下什么是平衡二叉树(引自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 }
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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。