剑指offer--面试题27：二叉搜索树与双向链表



题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。 python实现： # -*- coding:utf-8 -*- # class TreeNode: #     def __init__(self, x): #         self.val = x #         self.left = None #         self.right = None class Solution:     last = None#全局变量     def Convert(self, pRootOfTree):         if pRootOfTree is None:             return None         self.convertBST2LinkedList(pRootOfTree)         p = self.last         while p:             if p.left:                 p = p.left             else:                 break         return p               def convertBST2LinkedList(self, curNode):         if curNode is None:             return         if curNode.left:             self.convertBST2LinkedList(curNode.left)         curNode.left = self.last         if self.last:             self.last.right = curNode         self.last = curNode#更新last指针           if curNode.right:             self.convertBST2LinkedList(curNode.right) c++实现： /* struct TreeNode {     int val;     struct TreeNode *left;     struct TreeNode *right;     TreeNode(int x) :             val(x), left(NULL), right(NULL) {     } };*/   class Solution {     //static TreeNode* last; public:        TreeNode* Convert(TreeNode* pRootOfTree)     {         if(pRootOfTree==NULL)             return NULL;         TreeNode* last = NULL;         convertBST2LinkedList(pRootOfTree, last);         TreeNode* p = last;         while(p){             if(p->left)                 p = p->left;             else                 break;         }         return p;     }           void convertBST2LinkedList(TreeNode* curNode, TreeNode* &last){         if(curNode==NULL)             return;         if(curNode->left)             convertBST2LinkedList(curNode->left, last);         curNode->left = last;         if(last)             last->right = curNode;         last = curNode;         if(curNode->right)             convertBST2LinkedList(curNode->right, last);                } };   //TreeNode* Solution::last = NULL;