随笔 - 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 阅读(629) 评论(0)  编辑  收藏 所属分类: 算法与数据结构


只有注册用户登录后才能发表评论。
网站导航: