题解 | #二叉搜索树与双向链表#
二叉搜索树与双向链表
https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5
关键点1:二叉搜索树的中序遍历有序
关键点2:为了进行节点的链接,应引入前一个节点的引用 prev
在中序遍历的过程中对两两节点进行链接
class Solution { public: void InOrder(TreeNode* cur, TreeNode*& prev) { if(cur == nullptr) { return; } InOrder(cur->left, prev); //当前节点的前驱指针应指向前一个遍历的节点 cur->left = prev; //前一个被遍历的节点的后继指针应指向当前节点 if(prev) { prev->right = cur; } prev = cur; InOrder(cur->right, prev); } TreeNode* Convert(TreeNode* pRootOfTree) { TreeNode* prev = nullptr; InOrder(pRootOfTree, prev); TreeNode* head = pRootOfTree; //找链表头节点以返回 while(head && head->left) { head = head->left; } return head; } };