By

文章目录
  1. 1. 题目
  2. 2. 解析
  3. 3. 代码
  4. 4. 参考

题目

怎样编写一个程序,把一个有序整数数组放到二叉树中?

解析

这里都说这个数组是有序了，想想二叉树中对应有序相关的，就是二叉搜索树了。
二叉搜索树的根节点大于左侧的值，同时又小于右侧的值，那这样正好取数组的中间值作为根节点
然后将两侧分别递归作为左右子节点即可。
这种方式建树的另一个好处就是将树还原成数组很方便：直接使用中序遍历或者用不开辟空间的方法

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 使用递归构建二叉树即可 
 * 这样左侧节点小于根节点，右侧节点大于根节点
 * 对应数组正好是中间的值以及两侧的值
 * @param a
 * @param left
 * @param right
 * @return
 */
public static TreeNode putArrayToTree(int[] a,int left,int right)
{
	if(left>right)
		return null;
	
	int m=left+(right-left)/2;//取中间位置
	TreeNode root=new TreeNode(a[m]);//就是根节点
	root.left=putArrayToTree(a,left,m-1);
	root.right=putArrayToTree(a,m+1,right);
	
	return root;
}


/**
 * 树的结构
 * @author yanyl
 *
 */
static class TreeNode{
	public int data;
	public TreeNode left,right;
	public TreeNode(int data)
	{
		this.data=data;
	}
}

参考

  • July 微软面试100题 第86题

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权

文章目录
  1. 1. 题目
  2. 2. 解析
  3. 3. 代码
  4. 4. 参考