二叉搜索树与双向链表

题目描述

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

二叉搜索树的定义：

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

所要求的为排序列表，根据二叉搜索树的定义我们可以知道，二叉搜索树的中序遍历便是有序的。所以我们可以中序遍历二叉树。

image

解法一：

通过递归不断地将节点与其排序好的左右子树连接

public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) {
            return null;
        }
        TreeNode res = ConvertCore(pRootOfTree);
        while(res.left != null) {
            res = res.left;
        }
        return res;
    }
    public TreeNode ConvertCore(TreeNode pRootOfTree) {
        if(pRootOfTree == null) {
            return null;
        }
        //获得排序好的左子树
        TreeNode left = ConvertCore(pRootOfTree.left);
        if(left != null) {
            //获得左子树的最右节点
            while(left.right != null) {
                left = left.right;
            }
            //将排序好的左子树与根节点连接
            left.right = pRootOfTree;
            pRootOfTree.left = left;
        }
        //获得排序好的右子树
        TreeNode right = ConvertCore(pRootOfTree.right);
        if(right != null) {
            //获得右子树的最左节点
            while (right.left != null) {
                right = right.left;
            }
            //将排序好的右子树与根节点连接
            pRootOfTree.right = right;
            right.left = pRootOfTree;
        }
        return pRootOfTree;
    }
}

解法二：

解法一中要不断地靠循环来确定左右子树的最右和最左节点，时间效率较低。我们知道，中序遍历过程是有序的，我们可以使用一个指针保存当前中序遍历的点，依次将中序遍历经过的点连接起来便可以得到有序的双向链表，省去了大量的循环操作。

public class Solution {
    TreeNode current = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) {
            return null;
        }
        ConvertCore(pRootOfTree);
        while(current.left != null) {
            current = current.left;
        }
        return current;
    }
    public void ConvertCore(TreeNode pRootOfTree) {
        if(pRootOfTree == null) {
            return ;
        }
        ConvertCore(pRootOfTree.left);
        //记录二叉搜索树中最左边的节点即最小节点
        if(current == null) {
            current = pRootOfTree;
        }
        //连入新节点并更新双向链表的最右节点
        else{
            current.right = pRootOfTree;
            pRootOfTree.left = current;
            current = pRootOfTree;
        }
        ConvertCore(pRootOfTree.right);
    }
}

在上面的代码中，使用current来记录已经转换好的链表的最后一个节点。 例如当前节点为10的时候，current为8，将10与8连接后，current更新为10。接着遍历右子树，右子树的第一个点为12，将10和12连接起来，current更新为12。以此类推。

解法三：

解法二中用一个current保存中序遍历经过的节点，在最后返回时仍需要通过循环从current获得初始节点，我们如果再用一个指针来保存初始节点，便可以免去 这个循环操作，在数据量较大时节省一部分时间。

public class Solution {
    //双向链表的头节点
    TreeNode left = null;
    //中序遍历中依次经过的点，相当于解法二的current
    TreeNode right = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) {
            return null;
        }
        Convert(pRootOfTree.left);
        //保存双向链表的头节点
        if(right == null) {
            left = pRootOfTree;
            right = pRootOfTree;
        }
        //中序遍历过程中进行连接，并更新已获得的双向链表的尾节点
        else {
            right.right = pRootOfTree;
            pRootOfTree.left = right;
            right = pRootOfTree;
        }
        Convert(pRootOfTree.right);
        return left;
    }
}