426. Convert Binary Search Tree to Sorted Doubly Linked List

摘要:
将BST转换为已排序的循环双链接列表。左驾驶指针与上一个和下一个双链接列表同名。让我们以下面的BST为例,它可能会帮助您了解

Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list.

Let's take the following BST as an example, it may help you understand the problem better:

 

426. Convert Binary Search Tree to Sorted Doubly Linked List第1张

 

We want to transform this BST into a circular doubly linked list. Each node in a doubly linked list has a predecessor and successor. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.

The figure below shows the circular doubly linked list for the BST above. The "head" symbol means the node it points to is the smallest element of the linked list.

 

426. Convert Binary Search Tree to Sorted Doubly Linked List第2张

 

Specifically, we want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. We should return the pointer to the first element of the linked list.

The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.

 

426. Convert Binary Search Tree to Sorted Doubly Linked List第3张

先通过recursion,inorder traverse得到doubly sorted linked list,再连接首尾

用dummy node处理corner case,prev从dummy开始

time: O(n), space: O(logn)

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
    Node prev = null;
    public Node treeToDoublyList(Node root) {
        if(root == null) {
            return root;
        }
        Node dummy = new Node(0, null, null);
        prev = dummy;
        inorder(root);
        Node head = dummy.right;
        head.left = prev;
        prev.right = head;
        return head;
    }
    
    public void inorder(Node cur) {
        if(cur == null) {
            return;
        }
        inorder(cur.left);
        prev.right = cur;
        cur.left = prev;
        prev = cur;
        inorder(cur.right);
    }
}

免责声明:文章转载自《426. Convert Binary Search Tree to Sorted Doubly Linked List》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇707. Design Linked List明确类和对象下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

mkfifo()函数

/********************************************************************************** Copyright: (C) 2013 fulinux<fulinux@sina.com>* All rights reserved.** Filename: mkfifo.c*...

sencha build模式时候包含自有文件的问题

sencha 在build的时候大家会发现没有把自定义引用的js啊,图片啊文件copy进去 这个需要在app.json中设置 "resources":["resources/img","resources/icons","resources/startup","resources/js","c.json"], 这样这几个文件夹或文件就会随着项目一起buil...

编程实现自定义解决方案

作者:朱金灿 来源:blog.csdn.net/clever101 一般开发我喜欢遵循下面的规范:在项目解决方案文件夹下建5个文件夹: 文件夹名 备注 src 存放解决方案的源代码 thirdparty 存放第三方库的源代码(无源码的就存放头文件) Doc 存放该项目的相关文档,我一般在Doc文件夹下又新建三...

13.5.3 用指针处理结构数组

13.5.3 用指针处理结构数组 - 51CTO.COM 13.5.3 用指针处理结构数组 2009-06-04 14:32 戴建华 电子工业出版社 我要评论(0) 字号:T | T 综合评级: 想读(0)在读(1)已读(4) 品书斋鉴(0) 已有5人发表书评 《C语言开发技术详解》第13章结构、联合和枚举,在C语言中,数据类型可分...

生存还是毁灭

生存还是毁灭 - 维基百科,自由的百科全书 生存还是毁灭 维基百科,自由的百科全书 跳转到: 导航,搜索 生存还是毁灭(To be, or not to be)是莎士比亚出戏哈姆雷特第三幕第一场,哈姆雷特王子一段句白的第一句;很多人也会用这句来指整段句白。它是世界文学中常见被引用的一句。而整段句白是: "To be, or not to b...

超柔磨绒印花空调被(200*230cm) 凡客诚品工商银行团购专区 VANCL凡客诚品

超柔磨绒印花空调被(200*230cm) -凡客诚品工商银行团购专区- VANCL凡客诚品 超柔磨绒印花空调被(200*230cm) 【工行团购】仅售49元!超柔磨绒印花空调被,采用印花工艺,将漂亮的图案与优质产品面料完美结合,无论在感观还是手感上,都得到最大程度体现。聚酯纤维当前合成纤维的第一大品种,具有良好的弹性和蓬松性,产品色泽柔和,透气性良好,酷夏必...

最新文章