package Leetcode;

/**

* @author zbl

* @version 1.0

* @content:输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

为了让您更好地理解问题，以下面的二叉搜索树为例：

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

* @date 2020/6/2 21:01

*/

public class Solutionmian36 {

public static class Node {

public int value;

public Node right;

public Node left;

public Node(int value)

{

this.value=value;

}

}

public static Node treeToDoublyList(Node root) {

//递归写法

if(root==null) return null;

Node[] res=process(root);

res[0].left=res[1];

res[1].right=res[0];

return res[0];

}

//返回以root作为根节点形成的双向链表的头结点以及最后一个结点

private static Node[] process(Node root){

Node[] res=new Node[2];

if(root==null) return res;

Node[] left=process(root.left);

Node[] right=process(root.right);

if(left[1]!=null)

left[1].right=root;

root.left=left[1];

root.right=right[0];

if(right[0]!=null)

right[0].left=root;

res[0]=left[0]!=null ? left[0]:root;//当子树返回的结果不为null的时候才能使res[0]=left[0]

res[1]=right[1]!=null ? right[1] : root ;//与上面同理

return res;

}

public static void main(String[] args) {

Node head = new Node(4);

head.left = new Node(2);

head.right = new Node(6);

head.left.left = new Node(1);

head.left.right = new Node(3);

head.right.left = new Node(5);

treeToDoublyList(head);

}

}