题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
解题思路
主要是分治的思想，值得注意的是ResultType我们返回一个头指针和一个尾指针。
class Solution {
static class ResultType {
Node first;
Node last;
public ResultType(Node first, Node last) {
this.first = first;
this.last = last;
}
}
public Node treeToDoublyList(Node root) {
if (root == null) return null;
ResultType result = helper(root);
result.last.right = result.first;
result.first.left = result.last;
return result.first;
}
public ResultType helper(Node root) {
if (root == null) return null;
ResultType left = helper(root.left);
ResultType right = helper(root.right);
ResultType result = new ResultType(null, null);
if (left == null) {
result.first = root;
} else {
result.first = left.first;
left.last.right = root;
root.left = left.last;
}
if (right == null) {
result.last = root;
} else {
result.last = right.last;
root.right = right.first;
right.first.left = root;
}
return result;
}
}
