Interview-Collection/ConvertBSTtoDoublyLinkedList.h at master · bluepp/Interview-Collection · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/*
  bluepp
  2014-12-30
  May the force be with me!

  Convert Binary Search Tree (BST) to Sorted Doubly-Linked List
*/


/* v2, my version */
//convert binary search tree to sorted doubly linked list

Node *TreeToList(Node *root)
{
    Node *head = NULL;

    _convert(root, NULL, head);
    return head;
}

void _convert(Node *p, Node *&prev, Node *&head)
{
    if (!p) return;

    _convert(p->left, prev, head);

    if (prev)
        p->left = prev;
    else
        head = p;

    Node *right = p->right;
    if (head)
    {
        head->left = p;
        p->right = head;
    }

    prev = p;

    _convert(right, prev, head);
}


/* http://leetcode.com/2010/11/convert-binary-search-tree-bst-to.html */
//convert binary search tree to sorted doubly linked list

Node *TreeToList(Node *root)
{
    Node *prev = NULL;
    Node *head = NULL;

    _convert(root, prev, head);

    return head;
}

void _convert(Node *p, Node *&prev, Node *&head)
{
    if (!p) return;

    _convert(p->left, prev, head);

    p->left = prev;
    if (prev)
        prev->right = p;
    else
        head = p;

    Node *right = p->right;
    head->left = p;
    p->right = head;

    prev = p
    _convert(right, prev, head);
}