root
BAN USERModified Morris traversal
BSTnode BSTtoDLL() {
BSTnode p = this;
BSTnode ppre=null;
while (p != null) {
if (p.left == null) {
p.left=ppre;
p = p.right;
}
else {
BSTnode temp = p.left;
BSTnode pre = null;
while (temp.right != null && temp.right != p) {
pre = temp;
temp = temp.right;
}
if (temp.right == null) {
temp.right = p;
temp.left = pre;
BSTnode pleft = p.left;
p.left=temp;
p=pleft;
} else {
ppre=p;
p = p.right;
}
}
}
p=this;
while (p.left != null)
p = p.left;
return p;
}
DLLnode DLLToBT(DLLnode head) {
if (head.prev == null && head.next == null)
return head;
DLLnode root = findMiddle(head);
DLLnode headL = head;
DLLnode headR = root.next;
root.prev.next = null;
headR.prev = null;
root.prev = DLLToBT(headL);
root.next = DLLToBT(headR);
return root;
}
private DLLnode findMiddle(DLLnode head) {
DLLnode ptrSlow = head;
DLLnode ptrFast = head;
while (ptrFast != null && ptrFast.next != null) {
ptrSlow = ptrSlow.next;
ptrFast = ptrFast.next.next;
}
return ptrSlow;
}
}
- root July 02, 2016