二叉搜索树与双向链表

核心就是中序遍历和辅助节点pre来保存上一个遍历的节点。
先右遍历，再处理节点，后左遍历，这样能返回正序的链表。

public class Solution {
    TreeNode pre = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null)
            return null;
        Convert(pRootOfTree.right);
        if(pre != null){
            pRootOfTree.right = pre;
            pre.left = pRootOfTree;
        }
        pre = pRootOfTree;
        Convert(pRootOfTree.left);
        return pre;
    }
}

class Solution {
    Node pre = null;
    Node head = null;
    public Node treeToDoublyList(Node root) {
        if(root == null)
            return null;
        dfs(root);
        pre.right = head;
        head.left = pre;
        return head;
    }

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

    }

}

这道题定义了两个辅助节点，中序返回来的结果也是倒序的，再处理第一个节点和最后一个节点的关系即可。