刚看见一个不错的恐怖片的海报 (转载)# Joke - 肚皮舞运动
x*1
1 楼
这应该是一道大公司面试常见题吧，网上没有找到满意的答案，所以发个贴讨论一下。
题目的意思是：pre-order travesal 一个 BST，将节点值保存在一个数组中。怎样通
过这个数组重建这棵BST。我能想到的最直接的方法就是一个节点一个节点的插入，复
杂度是nlog(n)。这题有没有O(n)解法？
void makeTree(int[] arr)
{
Node root = null;
for(int i = 0; i
}
}
void insertNode(Node treeNode, int value)
{
if (treeNode == null)
treeNode = new Node(value);
else if (value < treeNode.value)
insertNode(treeNode.left, value);
else
insertNode(treeNode.right, value);
}
题目的意思是：pre-order travesal 一个 BST，将节点值保存在一个数组中。怎样通
过这个数组重建这棵BST。我能想到的最直接的方法就是一个节点一个节点的插入，复
杂度是nlog(n)。这题有没有O(n)解法？
void makeTree(int[] arr)
{
Node root = null;
for(int i = 0; i
}
}
void insertNode(Node treeNode, int value)
{
if (treeNode == null)
treeNode = new Node(value);
else if (value < treeNode.value)
insertNode(treeNode.left, value);
else
insertNode(treeNode.right, value);
}
