题目

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

思路

理解题意:

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

那么:

  • 第一步:利用递归 / 非递归中序遍历,存在一个数组 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);
    }
}

总结

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

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