[Yahoo][笔试] 把BST转换为双向链表

给出一棵BST，将其转换为双向链表，left保存前节点，right保存后节点。

例如：

/ \

1 7

/ \ / \

0 2 5 8

\ \ \

3 6 9

变为：0<->1<->2<->3<->4<->5<->6<->7<->8<->9.

解答：这里我们可以看到一个节点的左子树的最后节点就是本节点的前驱，右子树的最左节点就是后继。于是需要一个函数能够返回这样的需求，也就有了一个可以返回本棵树的左右节点的函数。

同时，在细节上进行一些处理。

 1 #include <iostream>
 2 using namespace std;
 3 
 4 struct Node
 5 {
 6     int val;
 7     Node *left;
 8     Node *right;
 9     Node():left(NULL), right(NULL){}
10 };
11 
12 struct LeftRightNode
13 {
14     Node *left;
15     Node *right;
16     LeftRightNode(){}
17     LeftRightNode(Node *l, Node *r):left(l), right(r){}
18 };
19 
20 LeftRightNode convert(Node *node)
21 {
22     if (node == NULL)
23     {
24         LeftRightNode ret;
25         return LeftRightNode(NULL, NULL);
26     }
27 
28     LeftRightNode leftTree = convert(node->left);
29     LeftRightNode rightTree = convert(node->right);
30 
31     node->left = leftTree.right;
32     if (leftTree.right)
33         leftTree.right->right = node;
34     
35     node->right = rightTree.left;
36     if (rightTree.left)
37         rightTree.left->left = node;
38 
39     Node *leftNode = leftTree.left ? leftTree.left : node;
40     Node *rightNode = rightTree.right ? rightTree.right : node;
41     return LeftRightNode(leftNode, rightNode);
42 }
43 
44 Node *convert2List(Node *head)
45 {
46     LeftRightNode ret = convert(head);
47 
48     return ret.left;
49 }
50 
51 void print(Node *node)
52 {
53     while(node)
54     {
55         cout << "Node val:" << node->val << " address:" << node << " left:" << node->left << " right:" << node->right << endl;
56         node = node->right;
57     }
58 }
59 
60 int main()
61 {
62     Node node[10];
63     for(int i = 0; i < 10; i++)
64         node[i].val = i;
65 
66     node[4].left = &node[1];
67     node[4].right = &node[7];
68 
69     node[1].left = &node[0];
70     node[1].right = &node[2];
71 
72     node[2].right = &node[3];
73 
74     node[7].left = &node[5];
75     node[7].right = &node[8];
76 
77     node[5].right = &node[6];
78 
79     node[8].right = &node[9];
80 
81     Node *head = convert2List(&node[4]);
82 
83     print(head);
84 }