import java.util.LinkedList;
public class CreateBSTfromSortedArray {
/**
* 题目:给定一个排序数组,如何构造一个二叉排序树
* 递归
*/
public static void main(String[] args) {
int[] data = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
CreateBSTfromSortedArray bst = new CreateBSTfromSortedArray();
Node root = bst.createBST(data);
bst.inOrder(root);
System.out.println();
bst.levelOrder(root);
}
public Node createBST(int[] data) {
if (data == null || data.length == 0) {
return null;
}
Node[] nodes = createNode(data);
return createBSTHelp(nodes, 0, data.length - 1);
}
//Recursion.Node[start...end],find its root.Then find left child and right child for the root.
public Node createBSTHelp(Node[] nodes, int start, int end) {
if (start > end) {
return null;
}
int mid = start + (end - start) / 2;
if (start == end) {
return nodes[mid];
}
Node root = nodes[mid];
root.left = createBSTHelp(nodes, start, mid - 1);
root.right = createBSTHelp(nodes, mid + 1, end);
return root;
}
public Node[] createNode(int[] data) {
int len = data.length;
Node[] nodes = new Node[len];
for (int i = 0; i < len; i++) {
nodes[i] = new Node(data[i]);
}
return nodes;
}
private static class Node {
int data;
Node left;
Node right;
Node(int data) {
this.data = data;
}
}
public void levelOrder(Node node) {
if (node == null)
return;
LinkedList<Node> queue = new LinkedList<Node>();
queue.addLast(node);
while (!queue.isEmpty()) {
Node curNode = queue.removeFirst();
System.out.print(curNode.data + " ");
if (curNode.left != null) {
queue.addLast(curNode.left);
}
if (curNode.right != null) {
queue.addLast(curNode.right);
}
}
}
public void inOrder(Node node) {
if (node == null) {
return;
}
inOrder(node.left);
System.out.print(node.data + " ");
inOrder(node.right);
}
}
分享到:
相关推荐
JAVA-SSH面试题JAVA-SSH面试题JAVA-SSH面试题JAVA-SSH面试题JAVA-SSH面试题JAVA-SSH面试题JAVA-SSH面试题JAVA-SSH面试题JAVA-SSH面试题JAVA-SSH面试题JAVA-SSH面试题JAVA-SSH面试题JAVA-SSH面试题JAVA-SSH面试题JAVA...
数组 - 需要参加面试的人
04-Java必知必会108题01-Java公司面试真题 02-Java面试文档 03-大数据面试文档 04-Java必知必会108题01-Java公司面试真题 02-Java面试文档 03-大数据面试文档 04-Java必知必会108题01-Java公司面试真题 02-Java面试...
JAVA-SSH面试题;JAVA-SSH面试题;JAVA-SSH面试题
最新各大公司企业真实面试题-Java面试题最新各大公司企业真实面试题-Java面试题
面试题53 - I. 在排序数组中查找数字 I题目链接面试题53 - I. 在排序数组中查找数字 I题目描述统计一个数字在排序数组中出现的次数。题解public
Java-常见面试题.pdf
JAVA-数据库面试题.docxJAVA-数据库面试题.docxJAVA-数据库面试题.docxJAVA-数据库面试题.docxJAVA-数据库面试题.docxJAVA-数据库面试题.docxJAVA-数据库面试题.docxJAVA-数据库面试题.docx
2024最新java-SSHM面试题整理.zip2024最新java-SSHM面试题整理.zip
JAVA-项目面试题.docx
java面试-Java+最常见的+200++面试题汇总+答案总结汇总 java面试-Java并发编程最全面试题 123道 java面试-Java集合框架常见面试题 java面试-Java虚拟机(JVM)面试题 51道 java面试-Kafka知识汇总 18道 java面试-...
java-android面试题
Java-Redis面试题
Java常见面试题集--面试题全面综合
Java-英文面试题-经典.docx