202407271307
tags: #linked-list

var treeToDoublyList = function(root) {
	if (root === null) {
		return null;
	}
	const leftHead = treeToDoublyList(root.left);
	const rightHead = treeToDoublyList(root.right);
	root.left = root;
	root.right = root;
	return connect(connect(leftHead, root), rightHead);
};

const connect = (n1, n2) => {
	if (n1 === null) {
		return n2;
	}
	if (n2 === null) {
		return n1;
	}
	const tail1 = n1.left;
	const tail2 = n2.left;
	tail1.right = n2;
	n2.left = tail1;
	tail2.right = n1;
	n1.left = tail2;
	return n1;
};

Reference

https://leetcode.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list