剑指 - 二叉搜索树与双向链表

题目

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

思路

理解题意：

• 虽然不能创建新的结点，但可以利用额外的数据结构来存储
• 二叉排序树：左孩子 < 根结点 < 右孩子，所以根据中序遍历，左中右，可以遍历到一个有序的序列

那么：

• 第一步：利用递归 / 非递归中序遍历，存在一个数组 or 一个队列
• 第二部：更新队列里的结点的 left and right 两个字段的引用，连成一条链表

class BiTreeAndDoubleLinkedList {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        return convert(pRootOfTree);
    }

    private TreeNode convert(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        LinkedList<TreeNode> queue = new LinkedList<>();
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            if (!stack.isEmpty()) {
                cur = stack.pop();
                queue.offer(cur);
                cur = cur.right;
            }
        }
        for (int i = 0; i < queue.size(); i++) {
            TreeNode left = i == 0 ? null : queue.get(i - 1);
            TreeNode right = i == queue.size() - 1 ? null : queue.get(i + 1);
            queue.get(i).left = left;
            queue.get(i).right = right;
        }
        return queue.get(0);
    }
}

总结

想了好久以为不用额外数据结构，不能创建新结点，得如何搞？？

后面受不了看看讨论区，发现原来可以用额外的数据结构存储结点，那就好搞了，顺别借这个机会复习一下非递归中序遍历二叉树~