美文网首页
面试题36(剑指offer)--二叉搜索树与双向链表

面试题36(剑指offer)--二叉搜索树与双向链表

作者: Tiramisu_b630 | 来源:发表于2019-08-14 10:28 被阅读0次

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

解法:

    private static TreeNode pre = null;//记录最后一个尾节点
    private static TreeNode head = null;//记录双向链表头结点

    public static TreeNode Convert(TreeNode pRootOfTree) {
        ConvertCore(pRootOfTree);
        return head;
    }

    private static void ConvertCore(TreeNode node) {//中序遍历二叉搜索树即为有序
        if (node == null)
            return;
        ConvertCore(node.left);
        node.left = pre;
        if (pre != null)
            pre.right = node;
        pre = node;
        if (head == null)
            head = node;
        ConvertCore(node.right);
    }

相关文章

网友评论

      本文标题:面试题36(剑指offer)--二叉搜索树与双向链表

      本文链接:https://www.haomeiwen.com/subject/hwgwjctx.html