将二叉搜索树转化为排序的双向链表

题目

将二叉搜索树转化为排序的双向链表

例如，下图二叉搜索树转换为图中的排序的双向链表。

一棵二叉搜索树

解析

转换为排序的双向链表，本质就是对二叉搜索树进行中序遍历。涉及中序遍历，自然有递归和非递归的解题方法。

• 递归方法：
  根节点root划分为左右两棵子树，root的左右指针分别指向左子树转换链表的尾节点和右子树转换链表的头节点，生成新的链表。左右两棵子树分别递归实现相同逻辑。
  递归终止条件是，如果root节点左子树为空，root节点就是其连接的新链表的头结点，如果root的右子树为空，root节点就是其连接的新链表的尾结点。
• 非递归方法：
  非递归中序遍历二叉搜索树，遍历的节点依次连接成一个双向的链表即可。

代码

递归方法

//递归实现
public Node convertBST2List(Node root){
    if (root == null){
        return null;
    }
    Node[] res = convertR(root);
    //返回新链表的头结点
    return res[0];
}

//递归方法，每次返回子树转换链表后的首尾两个节点
public Node[] convertR(Node root){
    Node[] res = new Node[2];
    //如果左子树不为null
    if (null != root.left){
        //递归转换左子树，得到左子树链表的首尾两个节点
        Node[] lres = convertR(root.left);
        //root与左子树链表的尾节点连接
        root.left = lres[1];
        lres[1].right = root;
        //root加入的新链表的头节点
        res[0] = lres[0];
    } else {
        //左子树为null，root加入的新链表的头节点就是root
        res[0] = root;
    }
    //root右子树不为null
    if (null != root.right){
        //递归转换右子树，得到右子树链表的首尾两个节点
        Node[] rres = convertR(root.right);
        //root与右子树链表的头结点连接
        root.right = rres[0];
        rres[0].left = root;
        //root加入的新链表的尾节点
        res[1] = rres[1];
    } else {
        //右子树为null，root加入的新链表的尾节点就是root
        res[1] = root;
    }
    //返回root连接的新链表的头尾节点
    return res;
}

非递归方法

关于中序遍历的非递归实现，参考Java二叉树相关知识

//非递归实现
public Node convert(Node root){
    if (null == root){
        return null;
    }
    Stack<Node> stack = new Stack<>();
    //定义最终链表的头尾指针
    Node head = new Node(), tail = head;
    //中序遍历的非递归实现
    while (null != root){
        while (null != root){
            stack.push(root);
            root = root.left;
        }
        while (!stack.empty() && null == root){
            //出栈，连接到新链表上
            root = stack.pop();
            tail.right = root;
            root.left = tail;
            tail = root;
            //出栈之后右拐
            root = root.right;
        }
    }
    return head.right;
}