【剑指offer】二叉搜索树转双向链表，C++实现

  1 /*
  2 struct TreeNode {
  3 	int val;
  4 	struct TreeNode *left;
  5 	struct TreeNode *right;
  6 	TreeNode(int x) :
  7 			val(x), left(NULL), right(NULL) {
  8 	}
  9 };*/

  1 /*
  2 struct TreeNode {
  3     int val;
  4     struct TreeNode *left;
  5     struct TreeNode *right;
  6     TreeNode(int x) :
  7             val(x), left(NULL), right(NULL) {
  8     }
  9 };*/
 10 class Solution {
 11 public:
 12     TreeNode* Convert(TreeNode* pRootOfTree)
 13     {/*
 14 struct TreeNode {
 15 	int val;
 16 	struct TreeNode *left;
 17 	struct TreeNode *right;
 18 	TreeNode(int x) :
 19 			val(x), left(NULL), right(NULL) {
 20 	}
 21 };*/
 22 class Solution {
 23 public:
 24     TreeNode* Convert(TreeNode* pRootOfTree)
 25     {
 26         // 双向链表尾节点
 27         TreeNode* list_last = nullptr;
 28 
 29         // 递归转换
 30         ConvertNode(pRootOfTree,list_last);
 31 
 32         // 双向链表首节点
 33         while(list_last->left != nullptr) // 边界条件
 34         {
 35             list_last = list_last->left;
 36         }
 37 
 38         // 返回双向链表的首节点
 39         return list_last;
 40     }
 41 
 42     void ConvertNode(TreeNode* cur,TreeNode* list_last)
 43     {
 44         // 边界条件
 45         if(cur==nullptr) return ;
 46 
 47         // 遍历左子树
 48         if(cur->left != nullptr) ConvertNode(cur->left,list_last);
 49 
 50         // 实现双向链接(建立连接)
 51         cur->left = list_last;
 52         if(list_last != nullptr) list_last->right = cur;
 53         list_last = cur;
 54 
 55         //遍历右子树
 56         if(cur->right != nullptr) ConvertNode(cur->right,list_last);
 57     }
 58 };
 59         if (pRootOfTree == NULL)return NULL;
 60 
 61         TreeNode *pointer = NULL;
 62 
 63         convert2List(pRootOfTree, pointer);
 64 
 65         while (pointer->left!=NULL)
 66         {
 67             pointer = pointer->left;
 68         }
 69         return pointer;
 70     }
 71     void convert2List(TreeNode* pRoot,TreeNode *&pointer)
 72     {
 73         if (pRoot == NULL)
 74         {
 75             return;
 76         }
 77         {
 78             if (pRoot->left != NULL)
 79             {
 80                 convert2List(pRoot->left,pointer);
 81             }
 82 
 83             pRoot->left = pointer;
 84             if (pointer != NULL)
 85             {
 86                 pointer->right = pRoot;
 87             }
 88 
 89             pointer = pRoot;
 90             if (pRoot->right!=NULL)
 91             {
 92                 convert2List(pRoot->right, pointer);
 93             }
 94         }
 95     }
 96 };