当前位置:首页 > 开发 > 编程语言 > Java > 正文

java-谷歌面试题-给定一个排序数组,如何构造一个二叉排序树

发表于: 2012-04-12   作者:bylijinnan   来源:转载   浏览:
摘要: import java.util.LinkedList; public class CreateBSTfromSortedArray { /** * 题目:给定一个排序数组,如何构造一个二叉排序树 * 递归 */ public static void main(String[] args) { int[] data = { 1, 2, 3, 4,
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-谷歌面试题-给定一个排序数组,如何构造一个二叉排序树

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
题目 一个大小为n的数组,里面的数都属于范围[0, n-1],有不确定的重复元素,找到至少一个重复元素
一 问题描述: 一个单词单词字母交换,可得另一个单词,如army->mary,成为兄弟单词。提供一个单
请用C语言实现 输出和为一个给定整数的所有组合 启动2012 <img alt="基于Visual C++2013拆解世界
转:http://www.cnblogs.com/jaic-xiao/archive/2008/09/23/1297320.html ASP.NET中的站点地图功能
转:http://www.cnblogs.com/jaic-xiao/archive/2008/09/23/search_zj_cnblogs_thanks__scott_mitch
ASP.NET中的站点地图功能与SiteMapPath, TreeView, 和 Menu控件帮助访问者浏览您的网站并找到信息。
谷歌公司的研究人员聆听了119个小时用户对移动网站的抱怨,了解到构建移动网站的精髓。   最近,
题目:输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的
【前沿】公司开发使用的是.Net Framework2.0的,所以不能用Linq,所以自己写了个排序并去重的方法!
二进制加法   任何一个二进制数都是由一个以上的比特组成,是一个比特串。为了突出组成它的每个比
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号