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

 

利用中序遍历法，记录一个前驱结点，然后将当前结点的左孩子指向前驱节点，这样的话，向左<---表示逆序，然后将前驱结点的右孩子指向当前节点-->，可以形成正序。

在这里记录的前驱节点不能在方法内部传递，不知道为什么

 

/**public class TreeNode {    int val = 0;    TreeNode left = null;    TreeNode right = null;    public TreeNode(int val) {        this.val = val;    }}*/public class Solution {    TreeNode pre = null;    public TreeNode Convert(TreeNode pRootOfTree) {        if(pRootOfTree == null) return null;        inOrder(pRootOfTree);        TreeNode res = pRootOfTree;        while(res.left != null){            res = res.left;        }        return res;    }    public void inOrder(TreeNode root){        if(root == null) return;        inOrder(root.left);        if(pre == null){            pre = root;        }else{            pre.right = root;            root.left = pre;            pre = root;        }        inOrder(root.right);    }}

　　

这样就不对，但是看C++的代码就是这样的，而且运行也正确，想不通

public class Solution {    public TreeNode Convert(TreeNode pRootOfTree) {        TreeNode pre = null;        inOrder(pRootOfTree, pre);        TreeNode res = pRootOfTree;       while(res.left!= null){           res = res.left;       }        return res;    }         public void inOrder(TreeNode root, TreeNode pre){        if(root == null) return;        inOrder(root.left, pre);        root.left = pre;        if(pre != null) pre.right = root;        pre = root;        inOrder(root.right, pre);    }}

　　

 可以AC的C++代码

class Solution {public:    TreeNode* Convert(TreeNode* pRootOfTree)    {        if(pRootOfTree == nullptr) return nullptr;        TreeNode* pre = nullptr;                  convertHelper(pRootOfTree, pre);                  TreeNode* res = pRootOfTree;        while(res ->left)            res = res ->left;        return res;    }          void convertHelper(TreeNode* cur, TreeNode*& pre)    {        if(cur == nullptr) return;                  convertHelper(cur ->left, pre);                  cur ->left = pre;        if(pre) pre ->right = cur;        pre = cur;                  convertHelper(cur ->right, pre);    }};