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.
思路: 通过Inorder traversal遍历Binary Search Tree, 同时维护preNode, 将preNode 和 当前的node像double linked list那样连起来。最后再将double linked list的head和tail连起来即可
Copy /*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node() {}
public Node(int _val,Node _left,Node _right) {
val = _val;
left = _left;
right = _right;
}
};
*/
class Solution {
public Node treeToDoublyList(Node root) {
if (root == null) {
return root;
}
Node[] preNode = new Node[1];
Node dummy = new Node(0, null, null);
preNode[0] = dummy;
inorderTraverse(root, preNode);
preNode[0].right = dummy.right;
dummy.right.left = preNode[0];
return dummy.right;
}
public void inorderTraverse(Node node, Node[] preNode) {
if (node == null) {
return;
}
inorderTraverse(node.left, preNode);
preNode[0].right = node;
node.left = preNode[0];
preNode[0] = node;
inorderTraverse(node.right, preNode);
}
}