b********e
发帖数: 693 | 1 那位大侠给一个?
再给一个linked list to balance BST的code吧
thanks |
y*********e
发帖数: 518 | 2 BST to Doubly Linked List:
public LinkedList convert(BTree tree) {
LinkedList list = new LinkedList();
convert(tree, list);
return list;
}
private void convert(BTree tree, LinkedList list) {
if (tree != null) {
convert(tree.getLeftChild(), list);
LinkedListNode node = new LinkedListNode(tree.getValue());
list.add(node); // append to tail
convert(tree.getRightChild(), list);
}
}
看起来很眼熟把？就是in-order的tree traverse而已。
至于LinkedList的实现。。
public cl
【在 b********e 的大作中提到】
: 那位大侠给一个?
: 再给一个linked list to balance BST的code吧
: thanks
|
y*********e
发帖数: 518 | 3 Doubly Linked List to Balanced BST:
取LinkedList的中间Node，那就是BST的Root。LinkedList的前半部分，就是BST的Left
Child；后半部分，就是BST的
Right Child。用递归。
public BTree convert(LinkedList list) {
if (list.size() > 0) {
// partition it into three parts: left, middle, right
Partition parts = partition(list);
LinkedList leftList = parts.getLeftSubList();
LinkedList rightList = parts.getRightSubList();
LinkedListNode middle = parts.getMiddle();
BTree root = new BTree(
【在 b********e 的大作中提到】
: 那位大侠给一个?
: 再给一个linked list to balance BST的code吧
: thanks
|
b*****n
发帖数: 221 | 4 如果不是sorted linked list,为什么不用linked list的root当BST的root?
Left
【在 y*********e 的大作中提到】
: Doubly Linked List to Balanced BST:
: 取LinkedList的中间Node，那就是BST的Root。LinkedList的前半部分，就是BST的Left
: Child；后半部分，就是BST的
: Right Child。用递归。
: public BTree convert(LinkedList list) {
: if (list.size() > 0) {
: // partition it into three parts: left, middle, right
: Partition parts = partition(list);
: LinkedList leftList = parts.getLeftSubList();
: LinkedList rightList = parts.getRightSubList();
|
y*********e
发帖数: 518 | 5 因为题目说了，要是 Balanced 的 BST
【在 b*****n 的大作中提到】
: 如果不是sorted linked list,为什么不用linked list的root当BST的root?
:
: Left
|
