二叉搜索树与双向链表 -- java

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

二叉树节点的定义如下：

public class BinaryTreeNode {
    int value;
    BinaryTreeNode left;
    BinaryTreeNode right;

    public BinaryTreeNode() {
    }

    public BinaryTreeNode(int value) {
        this.value = value;
    }
}

首先我们一定要想到用中序遍历二叉树。

1. 关键：设置一个末尾节点指针用来串联根节点的两侧连接
2. 先将左子树遍历完，然后末尾节点指针将指向左子树的最右侧,然后根节点的左指针就指向了末尾节点
3. 当右子树的最左侧遍历完之后，右子树的最左侧的节点的左指针就将指向根节点（此时的末尾节点）

public class Convert {
    // 链表中最后一个节点
    private static BinaryTreeNode lastNodeInList;

    // 给用户调用的
    public static BinaryTreeNode convert(BinaryTreeNode root) {
        lastNodeInList = null;

        convertNode(root);

        // lastNodeInList指向双向链表的尾结点
        // 我们需要返回头结点
        BinaryTreeNode firstNode = lastNodeInList;
        while (firstNode != null && firstNode.left != null) {
            firstNode = firstNode.left;
        }
        return firstNode;
    }

    // 辅助程序-核心
    private static void convertNode(BinaryTreeNode node) {
        // 递归结束的条件
        if (node == null) {
            return;
        }

        BinaryTreeNode current = node;
        if (current.left != null) {
            convertNode(current.left);
        }

        // 双向节点的赋值
        current.left = lastNodeInList;
        if (lastNodeInList != null) {
            lastNodeInList.right = current;
        }

        lastNodeInList = current;

        if (current.right != null) {
            convertNode(current.right);
        }
    }

    // 测试
    public static void main(String[] args) {
        BinaryTreeNode node1 = new BinaryTreeNode(10);
        BinaryTreeNode node2 = new BinaryTreeNode(6);
        BinaryTreeNode node3 = new BinaryTreeNode(14);
        BinaryTreeNode node4 = new BinaryTreeNode(4);
        BinaryTreeNode node5 = new BinaryTreeNode(8);
        BinaryTreeNode node6 = new BinaryTreeNode(12);
        BinaryTreeNode node7 = new BinaryTreeNode(16);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;

        BinaryTreeNode root = convert(node1);
        while (root != null) {
            System.out.print(root.value + "t");
            root = root.right;
        }
        // 输出 4	6	8	10	12	14	16
    }
}

《剑指Offer》
Coding-Interviews/二叉搜索树与双向链表.md at master · todorex/Coding-Interviews