题目
Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list.
答案
很暴力的思路，很多题都可以用, 不过不符合in-place的要求
class Solution {
public Node treeToDoublyList(Node root) {
if(root == null) return null;
// Use an array list to store all treenodes in sorted order
List<Node> list = new ArrayList<>();
recur(root, list);
for(int i = 0; i < list.size() - 1; i++) {
Node curr = list.get(i);
Node next = list.get(i + 1);
curr.right = next;
next.left = curr;
}
Node first = list.get(0);
Node last = list.get(list.size() - 1);
first.left = last;
last.right = first;
return first;
}
public void recur(Node root, List<Node> list) {
if(root == null) return;
recur(root.left, list);
list.add(root);
recur(root.right, list);
}
}
这个思路不难想，但是需要用global var
基本就是in order traversal过一遍BST,在途中连接上一个访问的结点和当前的结点
class Solution {
Node zero = null;
Node curr = null;
public Node treeToDoublyList(Node root) {
if(root == null) return null;
Node zero = new Node(0);
curr = zero;
recur(root);
curr.right = zero.right;
zero.right.left = curr;
return zero.right;
}
public void recur(Node root) {
if(root == null) return;
recur(root.left);
curr.right = root;
root.left = curr;
curr = root;
recur(root.right);
}
}