剑指offer第26题:二叉搜索树与双向链表
题目描述
二叉搜索树与双向链表
源码
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
TreeNode* Convert(TreeNode* pRoot)
{
if(pRoot == NULL) return NULL;
if(pRoot->left ==NULL && pRoot->right == NULL) return pRoot;
TreeNode * left = Convert(pRoot->left);
TreeNode * p = left;
while(p!=NULL && p->right != NULL) p = p->right;
if(p != NULL) {p->right = pRoot;pRoot->left = p;}
TreeNode * right = Convert(pRoot->right);
p = right;
if(p != NULL) {p->left = pRoot;pRoot->right = p;}
return left!=NULL?left:pRoot;
}
};