剑指Offer25 二叉搜索树转换为排序双向链表

  1 /*************************************************************************
  2     > File Name: 25_BSTConvert.cpp
  3     > Author: Juntaran
  4     > Mail: JuntaranMail@gmail.com
  5     > Created Time: 2016年08月31日 星期三 15时06分28秒
  6  ************************************************************************/
  7 
  8 #include <stdio.h>
  9 #include <malloc.h>
 10 
 11 // 二叉树结构体
 12 struct TreeNode
 13 {
 14     int val;
 15     TreeNode* left;
 16     TreeNode* right;
 17 };
 18 
 19 // 构造二叉搜索树
 20 TreeNode* InsertNode(TreeNode* tree, int val)
 21 {
 22     if (tree == NULL)
 23     {
 24         tree = new TreeNode();
 25         tree->left = NULL;
 26         tree->right = NULL;
 27         tree->val = val;
 28     }
 29     else if (tree->val > val)
 30         tree->left = InsertNode(tree->left, val);
 31     else if (tree->val < val)
 32         tree->right = InsertNode(tree->right, val);
 33     return tree;
 34 }
 35 
 36 void PrintTree(TreeNode* tree)
 37 {
 38     if (tree == NULL)
 39         return;
 40     PrintTree(tree->left);
 41     printf("%d ", tree->val);
 42     PrintTree(tree->right);
 43 }
 44 
 45 void PrintList(TreeNode* list)
 46 {
 47     printf("
");
 48     if (list == NULL)
 49         return;
 50     TreeNode* node = list;
 51     while (node)
 52     {
 53         printf("%d ", node->val);
 54         node = node->right;
 55     }
 56     printf("
");
 57 }
 58 
 59 /************************************************************************/
 60 // 剑指Offer写法
 61 void ConvertNode(TreeNode* node, TreeNode** last)
 62 {
 63     if (node == NULL)
 64         return;
 65     
 66     TreeNode* current = node;
 67     
 68     // 对tree的左子树进行转换，last是转换后链表最后一个结点的指针
 69     if (current->left != NULL)
 70         ConvertNode(current->left, last);
 71     // 调整tree的left指针，指向上一个结点
 72     current->left = *last;
 73     // 调整指向最后一个结点，right指向下一个结点
 74     if (*last != NULL)
 75         (*last)->right = current;
 76     
 77     // 调整指向最后链表一个结点的指针
 78     *last = current;
 79     
 80     // 对tree的右子树进行转换，last是转换后链表最后一个结点的指针
 81     if (current->right != NULL)
 82         ConvertNode(current->right, last);
 83 }
 84 
 85 // 二叉搜索树转换为排序双向链表
 86 TreeNode* Convert(TreeNode* root)
 87 {
 88     if (root == NULL)
 89         return NULL;
 90     
 91     TreeNode* last = NULL;
 92     ConvertNode(root, &last);
 93     
 94     TreeNode* head = root;
 95     // 找到最左边的结点，即转换后链表的头结点
 96     while (head && head->left)
 97         head = head->left;
 98     return head;
 99 }
100 /************************************************************************/
101 
102 /************************************************************************/
103 // 一个递归写法
104 
105 TreeNode* leftLast = NULL;
106 TreeNode* Convert2(TreeNode* root)
107 {
108     if (root == NULL)
109         return root;
110     if (root->left==NULL && root->right==NULL)
111     {
112         leftLast = root;
113         return root;
114     }
115     
116     // 左子树改造为双链表
117     TreeNode* left = Convert2(root->left);
118     // 左子树链表不为空，root追加到左子树链表
119     if (left != NULL)
120     {
121         leftLast->right = root;
122         root->left = leftLast;        // 构造双向链表
123     }
124     leftLast = root;
125     // 右子树改造为双链表
126     TreeNode* right = Convert2(root->right);
127     // 右子树链表不为空，链表追加到root后
128     if (right != NULL)
129     {
130         right->left = root;
131         root->right = right;
132     }
133     return left != NULL ? left : root;
134 }
135 /************************************************************************/
136 
137 int main()
138 {
139     TreeNode* tree = NULL;
140     for (int i = 10; i > 5; --i)
141     {
142         tree = InsertNode(tree, i);
143     }
144     for (int i = 0; i <= 5; ++i)
145     {
146         tree = InsertNode(tree, i);
147     }
148     PrintTree(tree);
149     // tree = Convert(tree);
150     tree = Convert2(tree);
151     PrintList(tree);
152     
153     return 0;
154 }