题解 | #二叉搜索树与双向链表#
二叉搜索树与双向链表
http://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5
class Solution
{
public:
TreeNode* Convert(TreeNode* pRootOfTree)
{
if(pRootOfTree == NULL) return NULL;
//cout<< pRootOfTree->val <<' ';
TreeNode* l = Convert(pRootOfTree->left); //l是左子树转换后的最左边结点
TreeNode *ans = l;
TreeNode* r = Convert(pRootOfTree->right);
//r是右子树转换后的最左边结点
if(l != NULL)
{
while(l->right != NULL) l=l->right;
l->right = pRootOfTree;
}
pRootOfTree ->left = l;
if( r!= NULL) r->left = pRootOfTree;
pRootOfTree -> right = r;
if(ans == NULL) ans = pRootOfTree;
return ans;
}
};
递归。
