426.二叉搜索树与双向链表

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

输入：[4,2,5,1,3]

输出：[1,2,3,4,5]

1. 一开始做法是想用线索二叉树的思路，把在左子树中的前驱找出来并指向当前节点，再出来进行一次遍历，把当前节点和在右子树的后继连起来。但后来改了几下发现很难实现，因为要找到后继关键是如何找到需要连接后继的节点。

• 在连接前驱时，如果仅仅修改前驱结点的right节点，那么向右遍历时，如果根据p.right.left!=p来判断是否是需要修改的节点的话，因为无法知道这个p.right是我们建立前驱添加的还是本来就有的，因此这个p.right.left可能在p的上面或者是下面，在上面的话需要修改的是p.right，在下面需要修改的是p。
• 如果连接前驱时，把前驱节点的right节点和当前节点的left都修改的话，那么找到需要修改节点时，真正的后继节点是找不到的，因为前面修改left后相当于断链，并且真正的后继节点没有被其他节点所指向，导致无法根据右子树的根找到后继。

2. dfs。这里比较难想的地方是用一个全局的pre节点来表示当前dfs搜索节点的前驱节点。中序遍历每次先搜索左子树，然后令当前节点为前驱节点(传给下面右子树)，然后搜索右子树。每次搜索只连接当前节点和前驱节点，因为连接当前节点的后继和右子树连接其前驱是一样的，保证工作的平均分配。

 Node pre,head;
 public Node treeToDoublyList(Node root) {
     if(root==null) return root;
     dfs(root);
     while(root.left!=null) root=root.left;
     head=root;
     head.left=pre;
     pre.right=head;
     return head;
 }
 public void dfs(Node root)
 {
     if(root==null) return ;
     dfs(root.left);
     if(pre!=null)
     pre.right=root;
     root.left=pre;
     pre=root;
     dfs(root.right); 
 }