w****x 发帖数: 2483 | 1 //Merge two BST
//O(n) solution
//1. Change BST into linked list
//2. Merge 2 linked lists
//3. Change linked list into a balanced BST
struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
////////////////////change BST to linked list///////////////////////////////
void _inner_chng_link(NODE* pNode, NODE*& ph, NODE*& pt)
{
if (NULL == pNode) return;
NODE* pLft1 = pNode;
NODE* pLft2 = pNode;
_inner_chng_link(pNode->pLft, pLft1, pLft2);
if (pNode != pLft2) //forget this link logic
{
pNode->pLft = pLft2;
pLft2->pRgt = pNode;
}
NODE* pRgt1 = pNode;
NODE* pRgt2 = pNode;
_inner_chng_link(pNode->pRgt, pRgt1, pRgt2);
if (pNode != pRgt1) //forget this link logic
{
pRgt1->pLft = pNode;
pNode->pRgt = pRgt1;
}
ph = pLft1;
pt = pRgt2;
}
NODE* ChngToLink(NODE* pRoot)
{
assert(pRoot);
NODE* ph = pRoot;
NODE* pt = pRoot;
_inner_chng_link(pRoot, ph, pt);
return ph;
}
//////////////////////////////////////////////////////////////////////////
///////////////////Merge 2 linked lists/////////////////////////////////
NODE* MergeLink(NODE* pHead1, NODE* pHead2)
{
assert(pHead1 && pHead2);
NODE* pNewHead = NULL;
NODE* pIter = NULL;
NODE* pIter1 = pHead1;
NODE* pIter2 = pHead2;
while (pIter1 != NULL && pIter2 != NULL)
{
NODE* pTmp = NULL;
if (pIter1->nVal <= pIter2->nVal)
{
pTmp = pIter1;
pIter1 = pIter1->pRgt;
}
else
{
pTmp = pIter2;
pIter2 = pIter2->pRgt;
}
if (pIter == NULL)
{
pNewHead = pTmp;
pIter = pTmp;
}
else
{
pIter->pRgt = pTmp;
pTmp->pLft = pIter;
pIter = pIter->pRgt;
}
}
if (pIter1 != NULL)
{
pIter->pRgt = pIter1;
pIter1->pLft = pIter;
}
if (pIter2 != NULL)
{
pIter->pRgt = pIter2;
pIter2->pLft = pIter;
}
return pNewHead;
}
//////////////////////////////////////////////////////////////////////////
////////////////Construct BST from linked list/////////////////////////////
NODE* _inner_construct(NODE* pHead, int nLen)
{
if (NULL == pHead || nLen <= 0)
return NULL;
NODE* pNode = pHead;
int nCount = (nLen + 1)/2;
for (int i = 1; i < nCount; i++)
pNode = pNode->pRgt;
pNode->pLft = _inner_construct(pHead, (nLen + 1)/2 - 1);
pNode->pRgt = _inner_construct(pNode->pRgt, nLen - (nLen + 1)/2);
return pNode;
}
NODE* ConstructBST(NODE* pHead)
{
assert(pHead);
int nLen = 0;
NODE* pIter = pHead;
while (pIter != NULL)
{
nLen++;
pIter = pIter->pRgt;
}
return _inner_construct(pHead, nLen);
}
//////////////////////////////////////////////////////////////////////////
NODE* MergeBST(NODE* pRoot1, NODE* pRoot2)
{
assert(pRoot1 && pRoot2);
NODE* ph1 = ChngToLink(pRoot1);
NODE* ph2 = ChngToLink(pRoot2);
NODE* ph = MergeLink(ph1, ph2);
return ConstructBST(ph);
}
---- 30 min with IDE |
y**********u 发帖数: 6366 | 2 我觉得唉
这个solution可能不对
谁都想得出来啊。。。
//
【在 w****x 的大作中提到】 : //Merge two BST : //O(n) solution : //1. Change BST into linked list : //2. Merge 2 linked lists : //3. Change linked list into a balanced BST : struct NODE : { : int nVal; : NODE* pLft; : NODE* pRgt;
|
p*****2 发帖数: 21240 | 3 不错。我也想做做呢。先mark一下。晚上我也试试。 |
w****x 发帖数: 2483 | 4 为啥不对, 这题就是把BST->linkedlist, merge linked list, construct balance
BST from linked list合起来 |
y**********u 发帖数: 6366 | 5 这样感觉就没什么意思了。。。就是基础题啊
【在 w****x 的大作中提到】 : 为啥不对, 这题就是把BST->linkedlist, merge linked list, construct balance : BST from linked list合起来
|
w****x 发帖数: 2483 | 6
写写看嘛~~~ 没那么基础. 我觉得一般公司这题够涮掉至少95%以上的人了
【在 y**********u 的大作中提到】 : 这样感觉就没什么意思了。。。就是基础题啊
|
p*****2 发帖数: 21240 | |
w****x 发帖数: 2483 | 8
面试给45分钟做这题
【在 p*****2 的大作中提到】 : 这么长,面试不死定了?
|
t*****2 发帖数: 9 | |
w****x 发帖数: 2483 | 10
BST自己就是linked list啊, vector要额外空间
【在 t*****2 的大作中提到】 : 为啥不用vector用linked list?
|
|
|
t********e 发帖数: 143 | 11 Maybe we can do 2 in order traversal at the same time and construct trees
from smallest element.
Here is a way to construct tree from smallest element:
http://www.leetcode.com/2010/11/convert-sorted-list-to-balanced |
p*****2 发帖数: 21240 | 12 写了一下BT 到 linkedlist不好写呀。
Node Convert(Node node)
{
Node head;
if (node.left == null)
head = node;
else
{
Pair1 pair = Change(node.left, null, node, true);
node.left = pair.max;
head = pair.min;
}
if (node.right != null)
{
Pair1 pair = Change(node.right, node, null, false);
node.right = pair.min;
}
return head;
}
Pair1 Change(Node node, Node prev, Node next, boolean left)
{
Pair1 pp = new Pair1(null, null);
if (node.left == null)
{
node.left = prev;
pp.min = node;
}
else
{
Pair1 pair = Change(node.left, prev, node, true);
node.left = pair.max;
pp.min = pair.min;
}
if (node.right == null)
{
node.right = next;
pp.max = node;
}
else
{
Pair1 pair = Change(node.right, node, next, false);
node.right = pair.min;
pp.max = pair.max;
}
return pp;
}
}
class Pair1
{
Node min;
Node max;
public Pair1(Node _min, Node _max)
{
min = _min;
max = _max;
}
}
class Node
{
int value;
Node left;
Node right;
public Node(int v)
{
value = v;
}
} |
w****x 发帖数: 2483 | 13
为啥总觉得你整地代码那么长呢...
用c做代码会短些
【在 p*****2 的大作中提到】 : 写了一下BT 到 linkedlist不好写呀。 : Node Convert(Node node) : { : Node head; : if (node.left == null) : head = node; : else : { : Pair1 pair = Change(node.left, null, node, true); : node.left = pair.max;
|
y**********u 发帖数: 6366 | 14 左括号占的行数比较多。。。
【在 w****x 的大作中提到】 : : 为啥总觉得你整地代码那么长呢... : 用c做代码会短些
|
p*****2 发帖数: 21240 | 15
算了。用C去面试吃了大亏了。用C当然是灵活很多了。有指针。
【在 w****x 的大作中提到】 : : 为啥总觉得你整地代码那么长呢... : 用c做代码会短些
|
b********h 发帖数: 2451 | 16
【在 w****x 的大作中提到】 : //Merge two BST : //O(n) solution : //1. Change BST into linked list : //2. Merge 2 linked lists : //3. Change linked list into a balanced BST : struct NODE : { : int nVal; : NODE* pLft; : NODE* pRgt;
|
p*****2 发帖数: 21240 | 17
我一直不习惯把左括号放到上一行,咋办呀。如果那样我看起程序来很费劲。
【在 y**********u 的大作中提到】 : 左括号占的行数比较多。。。
|
w****x 发帖数: 2483 | |
y**********u 发帖数: 6366 | 19 其实我觉得不比你的长啊
而且你的参数传递是指针类型的引用。。。
【在 w****x 的大作中提到】 : 除了这个括号外我还是觉得太多了
|
b********h 发帖数: 2451 | 20 不能直接用树?为啥要转换成linked list呢?
【在 w****x 的大作中提到】 : //Merge two BST : //O(n) solution : //1. Change BST into linked list : //2. Merge 2 linked lists : //3. Change linked list into a balanced BST : struct NODE : { : int nVal; : NODE* pLft; : NODE* pRgt;
|
l*********8 发帖数: 4642 | 21 转换成linked list后是O(N)算法
直接从一个bst逐个取出node插入到另一个bst,是O(N*logN)算法
【在 b********h 的大作中提到】 : 不能直接用树?为啥要转换成linked list呢?
|