JobHu

隨筆 - 8, 文章 - 0, 評(píng)論 - 6, 引用 - 0

數(shù)據(jù)加載中……

二叉排序樹變?yōu)殡p向鏈表

把一個(gè)二叉排序樹(也許不叫這個(gè))變?yōu)檫f增的雙向鏈表,不能夠生成額外的結(jié)點(diǎn).
eg 6
       / \
      4   8
     / \ / \
    3 5 7 9

3=4=5=6=7=8=9

我的解:

class Node

{

public Node left;

public Node right;

private static Node getLinkListTail(Node head)

{

Node result = head;

if(result==null) return null;

while(result.right!=null)

{

result = result.right;

}

return result;

}

public static Node flatten(Node root)

{

if(root==null) return null;

Node result = root;

// A leaf node

if(root.left==null&&root.right==null) return root;

//divide-and-conquer

Node leftSubTreeLinkListHead = flatten(root.left);

Node rightSubTreeLinkListHead = flatten(root.right);

//merge

Node leftSubTreeLinkListTail = getLinkListTail(leftSubTreeLinkListHead);

root.left = leftSubTreeLinkListTail;

root.right = rightSubTreeLinkListHead;

if(leftSubTreeLinkListHead!=null)

{

result = leftSubTreeLinkListHead;

leftSubTreeLinkListTail.right = root;

}

if(rightSubTreeLinkListHead!=null) rightSubTreeLinkListHead.left = root;

return result;

}

posted on 2007-07-18 20:37 Job Hu 閱讀(648) 評(píng)論(0) 編輯收藏所屬分類: 算法與數(shù)據(jù)結(jié)構(gòu)

新用戶注冊(cè) 刷新評(píng)論列表


只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。




網(wǎng)站導(dǎo)航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關(guān)文章: 實(shí)現(xiàn)一個(gè)棧,使其push,pop,min(取得棧中的最小元素)均為O(1) 二叉排序樹變?yōu)殡p向鏈表

JobHu

二叉排序樹變?yōu)殡p向鏈表

導(dǎo)航

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜