由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - BST to double linked list的code
相关主题
今天没心情看书,上来聊聊我这1个半月都干嘛了哪个高手能指出我程序的问题 (20几行的代码)
Some coding problems from Amazongoogle phone interview
ms面试题问道关于LRU的题目
为什么我做了快1000道题了,还是不行呢?!一个Java面试题目
convert bst to doubly linked list 求个干净容易理解的答案求leetcode LRU Java 解法
请问如何求binary tree的lowest common ancestorvm onsite 面经
一道G家题目careerup 2.4的答案是不是不对呀?!
BST和有序双向链表的相互转换?150上这个是不是不对? (转载)
相关话题的讨论汇总
话题: bst话题: linkedlist话题: list话题: linked话题: btree
进入JobHunting版参与讨论
1 (共1页)
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

1 (共1页)
进入JobHunting版参与讨论
相关主题
150上这个是不是不对? (转载)convert bst to doubly linked list 求个干净容易理解的答案
Amazon电面面经(1面和2面)请问如何求binary tree的lowest common ancestor
Rejected After 2nd Phone Interview with Amazon一道G家题目
攒人品,发MS面筋BST和有序双向链表的相互转换?
今天没心情看书,上来聊聊我这1个半月都干嘛了哪个高手能指出我程序的问题 (20几行的代码)
Some coding problems from Amazongoogle phone interview
ms面试题问道关于LRU的题目
为什么我做了快1000道题了,还是不行呢?!一个Java面试题目
相关话题的讨论汇总
话题: bst话题: linkedlist话题: list话题: linked话题: btree