剑指Offer - 九度1503 - 二叉搜索树与双向链表

剑指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表示树的节点个数。
剑指Offer - 九度1503 - 二叉搜索树与双向链表
  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("\n");
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("\n");
134             deleteList(left_most);
135             root = left_most = right_most = NULL;
136         }
137     }
138 
139     return 0;
140 }
剑指Offer - 九度1503 - 二叉搜索树与双向链表

剑指Offer - 九度1503 - 二叉搜索树与双向链表

上一篇:对焦模式与区域模式总结


下一篇:剑指Offer - 九度1504 - 把数组排成最小的数