二叉搜索树与双向链表

题目：

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

解题思路：

由于二叉树的中序遍历具有可以实现递增的功能，同时二叉树的每一个节点都有两个指针，左指针和右指针，因此我们可以用这些特点将二叉树转换成一个双向链表，每次在递归遍历的时候设置一个pre，记录中序遍历时当前节点的前节点，然后将当前节点的左指针指向pre节点，然后如果pre节点不为空则将pre的右节点指向当前节点，由此就形成了一个双向链表的前后指针。每次递归重复这两步，则可以形成一个完整的双向链表。

最后一步就是双向链表已经构建完成了，而题目要求返回双向链表，则从原二叉树的root节点往前遍历找到双向链表的头返回即可。、

代码：

代码中设置了一个只有一个空间的数组来保存pre节点。

public TreeNode Convert(TreeNode pRootOfTree) {
    if (pRootOfTree == null) {
        return pRootOfTree;
    }
    TreeNode[] pre = new TreeNode[1];
    helper(pRootOfTree, pre);
    //已经完成双向链表的链接，找链表头节点返回
    TreeNode p = pRootOfTree;
    while (p.left != null) {
        p = p.left;
    }
    return p;
}
private void helper(TreeNode root, TreeNode[] pre) {
    if (root.left != null) {
        helper(root.left, pre);
    }
    root.left = pre[0];  //设置left指向前一个节点
    if (pre[0] != null) {
        pre[0].right = root;  //pre right指向root
    }
    //记录当前节点为尾节点
    pre[0] = root;
    if (root.right != null) {
        helper(root.right, pre);
    }
}

-----------EOF-----------