二叉搜索树与双向链表
题目链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
思路:关键在于如何建立二叉搜索树与排序双向链表之间的关系。排序链表的建立可以视为一组数字从小到大依次指向下一个数字节点,因此对应到二叉搜索树上就是中序遍历。
- 每一次操作都是pre的右指针指向curr,curr的左指针指向pre
- 注意头尾指针要单独处理,当中序遍历递归结束时pre即为最后一个节点
参考代码:
class Solution {
private:
Node* pre;
Node* head;
public:
Node* treeToDoublyList(Node* root) {
if (!root) {
return NULL;
}
dfs(root);
head->left = pre;
pre->right = head;
return head;
}
void dfs(Node* curr) {
if (!curr) {
return;
}
dfs(curr->left);
if (!pre) {
head = curr;
}
else {
pre->right = curr;
}
curr->left = pre;
pre = curr;
dfs(curr->right);
}
};