JobHu

隨筆 - 8, 文章 - 0, 評論 - 6, 引用 - 0

數據加載中……

二叉排序樹變為雙向鏈表

把一個二叉排序樹(也許不叫這個)變為遞增的雙向鏈表,不能夠生成額外的結點.
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) 評論(0) 編輯收藏所屬分類: 算法與數據結構

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關文章: 實現一個棧,使其push,pop,min(取得棧中的最小元素)均為O(1) 二叉排序樹變為雙向鏈表

JobHu

二叉排序樹變為雙向鏈表

導航

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜