数据结构-二分搜索树转双向链表（Java）

二分搜索树转双向链表（牛客JZ36）
题目

思路
1，对二分搜索树进行中序遍历
2，将二分搜索树左节点和根节点相连接，右节点和根节点相连接
遍历左子树，连接（左子树尾部不为空）
leftTail.right = pRootOfTree;
pRootOfTree.left = leftTail;
遍历右子树，连接
right.left = pRootOfTree;
pRootOfTree.right = right;

代码实现

 public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null ||(pRootOfTree.left == null && pRootOfTree.right == null)){
            return pRootOfTree;
        }
        TreeNode left = Convert(pRootOfTree.left);
        TreeNode leftTail = left;
        while(leftTail != null && leftTail.right != null){
            leftTail = leftTail.right;
        }
        //将二分搜索树左节点和根节点相连
        //左子树尾部不为空
        if(leftTail != null) {
            leftTail.right = pRootOfTree;
            pRootOfTree.left = leftTail;
        }
        TreeNode right = Convert(pRootOfTree.right);
        //将二分搜索树右节点和根节点相连
         if(right != null){
             right.left = pRootOfTree;
             pRootOfTree.right = right;
         }
        return left == null?pRootOfTree:left;
    }