【二叉搜索树】转排序双向链表
var treeToDoublyList = function(root) {
if(!root) return null;
let head = null,tail = null,pre = null;
function dfs(root){
if(!root) return null;
dfs(root.left);
//第一个节点作为头节点
if(!pre) head = root;
//将上一个节点的后继指针指向当前节点
else pre.right = root;
//将当前指针的前驱指针指向上一个节点
root.left = pre;
//更新上一个节点
pre = root;
//更新尾部节点
tail = root;
dfs(root.right);
}
dfs(root);
//首尾连接
head.left = tail;
tail.right = head;
return head;
};
最后更新于