剑指Offer

剑指Offer - 九度1503 - 二叉搜索树与双向链表
2014-02-05 23:39

题目描述：: 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

输入：: 输入可能包含多个测试样例。
对于每个测试案例，输入的第一行为一个数n(0<n<1000)，代表测试样例的个数。
接下来的n行，每行为一个二叉搜索树的先序遍历序列，其中左右子树若为空则用0代替。

输出：: 对应每个测试案例，
输出将二叉搜索树转换成排序的双向链表后，从链表头至链表尾的遍历结果。

样例输入：

1
2 1 0 0 3 0 0

样例输出：

1 2 3

题意分析：
　　这道题要求将二叉搜索树转换成双向链表，我的思路是进行后序遍历。先将左右子树搞定以后，再处理根节点。
　　那么，怎么处理呢？在转换完成之后，根节点的左边是左子树最大的节点(左子树最偏右的)，右边是右子树最小的节点(右子树最偏左的)。
　　因此，在递归过程中，需要获得这两个参数，具体做法请参见代码。其中最关键的四个参数：
　　　　1. pll：左子树最靠左的节点
　　　　2. plr：左子树最靠右的节点
　　　　3. prl：右子树最靠左的节点
　　　　4. prr：右子树最靠右的节点
　　虽然也可以通过O(h)的复杂度(h为树的高度)查找出上述四个节点，但那么做的话，就重复遍历了很多节点，整体复杂度也变成了O(n * log(n))。
　　所以我们在递归的过程中随时更新这些参数即可。
　　时间复杂度为O(n)，空间复杂度O(n)，n表示树的节点个数。

  1 // 690545    zhuli19901106    1503    Accepted    点击此处查看所有case的执行结果    1024KB    2642B    70MS
  2 // 201402041916
  3 //#define MY_DEBUG
  4 #include <cstdio>
  5 #include <cstring>
  6 #include <vector>
  7 using namespace std;
  8 
  9 typedef struct st{
 10 public:
 11     int key;
 12     struct st *ll;
 13     struct st *rr;
 14     st(int _key): key(_key) {}
 15 }st;
 16 
 17 void convertBSTtoDoubleLinkedList(st *root, st *&left_most, st *&right_most)
 18 {
 19     if (root == NULL) {
 20         return;
 21     }
 22 
 23     if (root->ll == NULL && root->rr == NULL) {
 24         left_most = root;
 25         right_most = root;
 26     }
 27 
 28     st *pll = NULL, *plr = NULL, *prl = NULL, *prr = NULL;
 29     if (root->ll != NULL) {
 30         convertBSTtoDoubleLinkedList(root->ll, pll, plr);
 31     } else {
 32         pll = plr = root;
 33     }
 34     if (root->rr != NULL) {
 35         convertBSTtoDoubleLinkedList(root->rr, prl, prr);
 36     } else {
 37         prl = prr = root;
 38     }
 39     left_most = pll;
 40     right_most = prr;
 41     if (plr != root) {
 42         plr->rr = root;
 43         root->ll = plr;
 44     }
 45     if (prl != root) {
 46         prl->ll = root;
 47         root->rr = prl;
 48     }
 49 }
 50 
 51 void constructBST(st *&root)
 52 {
 53     int tmp;
 54 
 55     scanf("%d", &tmp);
 56     if (tmp == 0) {
 57         root = NULL;
 58     } else {
 59         root = new st(tmp);
 60         constructBST(root->ll);
 61         constructBST(root->rr);
 62     }
 63 }
 64 
 65 #ifdef MY_DEBUG
 66 void postorderTraversal(const st *root)
 67 {
 68     if (root == NULL) {
 69         return;
 70     }
 71     postorderTraversal(root->ll);
 72     postorderTraversal(root->rr);
 73     printf("%d ", root->key);
 74 }
 75 #endif
 76 
 77 st *deleteList(st *head)
 78 {
 79     if (NULL == head) {
 80         return head;
 81     }
 82     st *ptr1, *ptr2;
 83 
 84     ptr1 = head;
 85     while (ptr1 != NULL) {
 86         ptr2 = ptr1;
 87         ptr1 = ptr1->rr;
 88         delete ptr2;
 89     }
 90 
 91     return NULL;
 92 }
 93 
 94 st *deleteTree(st *root)
 95 {
 96     if (NULL == root) {
 97         return NULL;
 98     }
 99     if (root->ll != NULL) {
100         root->ll = deleteTree(root->ll);
101     }
102     if (root->rr != NULL) {
103         root->rr = deleteTree(root->rr);
104     }
105     delete root;
106     return NULL;
107 }
108 
109 int main()
110 {
111     int cc, ci;
112     st *root = NULL;
113     st *left_most, *right_most, *ptr;
114 
115     while (scanf("%d", &cc) == 1) {
116         for (ci = 0; ci < cc; ++ci) {
117             root = NULL;
118             constructBST(root);
119 
120             // used to verify the tree
121             #ifdef MY_DEBUG
122             postorderTraversal(root);
123             printf("
");
124             #endif
125 
126             left_most = right_most = NULL;
127             convertBSTtoDoubleLinkedList(root, left_most, right_most);
128             ptr = left_most;
129             while (ptr != NULL) {
130                 printf("%d ", ptr->key);
131                 ptr = ptr->rr;
132             }
133             printf("
");
134             deleteList(left_most);
135             root = left_most = right_most = NULL;
136         }
137     }
138 
139     return 0;
140 }