如何在O(N)时间构建二叉树?

本文介绍了如何在O(N)时间构建二叉树?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

接着上一个问题在这里我很想知道如何从N个未排序的大整数的数组中按N个时间构建一个二叉树?

Following on from a previous question here I'm keen to know how to build a binary tree from an array of N unsorted large integers in order N time?

推荐答案

确定，仅出于完整性考虑...有问题的二进制树是从数组构建的，每个数组元素都有一个叶子.它使它们保持原始的 index 顺序，不值顺序，因此，它不能神奇地使您按线性时间对列表进行排序.它还需要保持平衡.

OK, just for completeness... The binary tree in question is built from an array and has a leaf for every array element. It keeps them in their original index order, not value order, so it doesn't magically let you sort a list in linear time. It also needs to be balanced.

要在线性时间内构建这样的树，您可以使用像这样的简单递归算法(使用从0开始的索引):

To build such a tree in linear time, you can use a simple recursive algorithm like this (using 0-based indexes):

//build a tree of elements [start, end) in array //precondition: end > start buildTree(int[] array, int start, int end) { if (end-start > 1) { int mid = (start+end)>>1; left = buildTree(array, start, mid); right = buildTree(array, mid, end); return new InternalNode(left,right); } else { return new LeafNode(array[start]); } }