题解 | #二叉搜索树与双向链表#
二叉搜索树与双向链表
https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: TreeNode* head; TreeNode* pre; TreeNode* Convert(TreeNode* pRootOfTree) { if (pRootOfTree==nullptr) { return nullptr; } Convert(pRootOfTree->left); if(pre==nullptr){ head = pRootOfTree; pre = pRootOfTree; } else { pre->right = pRootOfTree; pRootOfTree->left = pre; pre = pRootOfTree; } Convert(pRootOfTree->right); return head; } };
使用中序递归遍历,遍历过程中更改当前节点的左为前树,前节点的右子树为当前节点