就地将 BST 转换为最小堆

2025年3月17日 | 阅读 7 分钟

问题陈述

将二叉搜索树转换为具有相同元素的最小堆，采用就地方法，并以线性时间复杂度 (O(n)) 完成此转换。

输入

        15
       /      \
    10       20
  /   \     /   \
 8     12  17    25

输出

       8
     /    \
   10       17
 /   \     /   \
15   12   20    25

同样，答案可以是任何符合最小堆原则的内容。

注意：在查看解决方案之前，请先尝试提出一种方法

方法1：朴素方法

使用额外空间

创建一个大小为N的数组arr，其中N表示给定BST中的节点数。
执行BST的中序遍历，将节点值按排序顺序存储在数组arr中。
继续进行树的先序遍历。
在先序遍历过程中遍历根节点时，系统地将数组arr中的值分配给BST的节点，确保每个节点的值都遵循最小堆所需的顺序。

伪代码

Node structure:
    data
    left
    right

Function: getNode
    Create a new node with the given data
    Set left and right pointers to NULL
    Return the newly created node

Function: inorderTraversal
    if the root is NULL, return
    inorderTraversal(root->left)
    Append root's data to arr
    inorderTraversal(root->right)

Function: BSTToMinHeap
    if the root is NULL, return
    Set root's data to arr[i]
    Increment i
    BSTToMinHeap(root->left)
    BSTToMinHeap(root->right)

Function: convertToMinHeapUtil
    Create an empty array are
    Initialize i to -1
    Perform inorderTraversal(root, arr)
    Perform BSTToMinHeap(root, arr, &i)

Function: preorderTraversal
    if root is NULL, return
    Print root's data
    preorderTraversal(root->left)
    preorderTraversal(root->right)

注意：尝试在不查看原始代码的情况下实现，通过参考上述伪代码来提高您的编码水平，如果遇到困难，请对照提供的解决方案来审查多种编写代码的方式。

通过采用这种方法，我们确保二叉搜索树根据指定的条件转换为最小堆，相应地保持元素的完整性和顺序。

上述方法的Java实现

import java.util.ArrayList;

// Class representing a node in the BST
class Node {
    int data;
    Node left, right;

    Node(int data) {
        this.data = data;
        left = right = null;
    }
}

// Main class to convert the given BST to Min Heap
public class BSTToMinHeapConversion {

    // Helper function to do inorder traversal and store the values in the array
    private static void inorderTraversal(Node root, ArrayList<Integer> arr) {
        if (root == null)
            return;

        // Recur on the left subtree
        inorderTraversal(root.left, arr);

        // Copy the data of the node
        arr.add(root.data);

        // Recur on the right subtree
        inorderTraversal(root.right, arr);
    }

    // Helper function to convert the BST to Min Heap
    private static void BSTToMinHeap(Node root, ArrayList<Integer> arr, int[] i) {
        if (root == null)
            return;

        // First, copy data at index 'i' of 'arr' to the node
        root.data = arr.get(++i[0]);

        // Recur on the left subtree
        BSTToMinHeap(root.left, arr, i);

        // Recur on the right subtree
        BSTToMinHeap(root.right, arr, i);
    }

    // Utility function to convert the given BST to Min Heap
    private static void convertToMinHeapUtil(Node root) {
        // ArrayList to store the data of all the nodes of the BST
        ArrayList<Integer> arr = new ArrayList<>();
        int[] i = {-1};

        // Inorder traversal to populate 'arr'
        inorderTraversal(root, arr);

        // BST to Min Heap conversion
        BSTToMinHeap(root, arr, i);
    }

    // Function for preorder traversal of the tree
    private static void preorderTraversal(Node root) {
        if (root == null)
            return;

        // First, print the root's data
        System.out.print(root.data + " ");

        // Recur on the left subtree
        preorderTraversal(root.left);

        // Recur on the right subtree
        preorderTraversal(root.right);
    }

    // Driver program to test above
    public static void main(String[] args) {
        // BST formation
        Node root = new Node(4);
        root.left = new Node(2);
        root.right = new Node(6);
        root.left.left = new Node(1);
        root.left.right = new Node(3);
        root.right.left = new Node(5);
        root.right.right = new Node(7);

        // Function call
        convertToMinHeapUtil(root);
        System.out.println("Preorder Traversal:");
        preorderTraversal(root);
    }
}

输出

说明

BSTToMinHeap方法递归地使用先序遍历将BST转换为最小堆。
它首先将ArrayList arr中索引i处的值分配给当前节点，然后更新索引（i[0]是一个数组，用于在递归调用中保持可变索引）。
然后它递归地处理左子树和右子树。
convertToMinHeapUtil方法作为实用函数，它初始化一个ArrayList来存储节点值，并通过调用inorderTraversal填充ArrayList和BSTToMinHeap执行转换来启动转换过程。

时间复杂度：O(N)

空间复杂度: O(N)

由于上述方法使用了辅助空间，因此您需要进一步优化解决方案。

方法2：（最优）

当允许使用额外内存时，我们可以对树执行中序遍历，并将键记录在一个单独的数组中。由于BST的特性，该数组将自然排序。随后，我们可以通过遍历排序数组并从左到右逐级构造节点来创建一棵完全二叉树。通过从排序数组中选择下一个最小元素，我们保证生成的二叉树遵循最小堆属性。此方法的时间复杂度为O(n)，但需要额外的空间用于数组存储，使其成为非就地解决方案。

为了实现二叉搜索树就地转换为排序链表，我们采用逆中序遍历。这包括以优先右子树而非左子树的方式遍历BST。在遍历过程中，我们将节点插入到现有链表的开头，并相应地调整头指针。通过执行此逆中序遍历并仔细管理节点插入，我们保持链表的排序顺序。此方法确保了内存的有效使用，而不依赖于额外的数据结构。

随后，我们继续将排序链表转换为最小堆。这种转换涉及仔细调整节点的左右指针以符合最小堆属性。为了实现这一点，我们对部分构造的最小堆树进行层序遍历。同时，我们同步遍历链表。在每一步中，我们将队列中的父节点指定为下一个两个来自链表的节点作为其子节点。然后将这些新分配的节点入队以进行进一步处理。这个过程在链表排序性质的支持下，保证了最小堆属性的保留。

希望您理解这种方法；下面是详细的算法，以供您的逻辑理解

BST就地转换为最小堆的算法

步骤 1：定义节点结构

定义一个具有整数数据以及指向左右子节点的指针的Node结构。

步骤 2：定义实用函数

定义一个实用函数newNode(data)来创建一个具有给定数据的新节点，将左右指针初始化为NULL。

步骤 3：将BST转换为排序链表

定义一个函数BSTToSortedLL(root, head_ref)来使用逆中序遍历将BST转换为排序链表。

基本情况：如果root为NULL，则返回。

递归调用BSTToSortedLL(root.right, head_ref)。

更新指针以将树转换为链表。

步骤 4：将排序链表转换为最小堆

定义一个函数SortedLLToMinHeap(root, head)来使用队列将排序链表转换为最小堆。

基本情况：如果head为NULL，则返回。

初始化一个队列。

将第一个节点作为最小堆的根节点开始。

遍历链表并使用队列设置左右子指针。

上述方法的Java实现

import java.util.LinkedList;
import java.util.Queue;

class TreeNode {
    int value;
    TreeNode left, right;

    // Constructor to initialize a TreeNode
    public TreeNode(int item) {
        value = item;
        left = right = null;
    }
}

public class BSTToMinHeapConverter {

    // Utility function to print the level order of a tree
    private static void printLevelOrder(TreeNode root) {
        if (root == null)
            return;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int nodeCount = queue.size();
            while (nodeCount > 0) {
                TreeNode node = queue.poll();
                System.out.print(node.value + " ");
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);
                nodeCount--;
            }
            System.out.println();
        }
    }

    // Convert the given BST to a sorted linked list
    private static void BSTToSortedLinkedList(TreeNode root, TreeNode[] headRef) {
        if (root == null)
            return;

        // Traverse the right subtree
        BSTToSortedLinkedList(root.right, headRef);

        // Insert the root into the linked list
        root.right = headRef[0];

        if (headRef[0] != null)
            headRef[0].left = null;

        // Update the head of the linked list
        headRef[0] = root;

        // Traverse the left subtree
        BSTToSortedLinkedList(root.left, headRef);
    }

    // Convert a sorted linked list to a min-heap
    private static void SortedLinkedListToMinHeap(TreeNode root, TreeNode head) {
        if (head == null)
            return;

        Queue<TreeNode> queue = new LinkedList<>();
        root = head;
        head = head.right;
        root.right = null;
        queue.add(root);

        while (head != null) {
            TreeNode parent = queue.poll();
            TreeNode leftChild = head;
            head = head.right;
            leftChild.right = null;
            queue.add(leftChild);
            parent.left = leftChild;

            if (head != null) {
                TreeNode rightChild = head;
                head = head.right;
                rightChild.right = null;
                queue.add(rightChild);
                parent.right = rightChild;
            }
        }
    }

    // Convert BST to Min-Heap in-place
    private static TreeNode BSTToMinHeap(TreeNode root) {
        TreeNode[] head = {null};
        BSTToSortedLinkedList(root, head);
        root = null;
        SortedLinkedListToMinHeap(root, head[0]);
        return head[0];
    }

    public static void main(String[] args) {
        /* Constructing below tree
                8
               / \
             4  12
            / \ / \
          2 6 10 14
        */

        TreeNode root = new TreeNode(8);
        root.left = new TreeNode(4);
        root.right = new TreeNode(12);
        root.right.left = new TreeNode(10);
        root.right.right = new TreeNode(14);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(6);

        // Convert the BST to a Min-Heap
        TreeNode minHeapRoot = BSTToMinHeap(root);

        /* Output - Min Heap
                2
               / \
              4  6
             / \ / \
          8 10 12 14
        */

        // Print the min-heap in level order
        printLevelOrder(minHeapRoot);
    }
}

输出

时间复杂度：O(n)

辅助空间： O(n)

下一主题波兰表示法和逆波兰表示法

就地将 BST 转换为最小堆

注意：在查看解决方案之前，请先尝试提出一种方法

注意：尝试在不查看原始代码的情况下实现，通过参考上述伪代码来提高您的编码水平，如果遇到困难，请对照提供的解决方案来审查多种编写代码的方式。

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

就地将 BST 转换为最小堆

注意：在查看解决方案之前，请先尝试提出一种方法

注意：尝试在不查看原始代码的情况下实现，通过参考上述伪代码来提高您的编码水平，如果遇到困难，请对照提供的解决方案来审查多种编写代码的方式。

相关帖子

创建具有 O 和 X 交替矩形的矩阵

合并两个二叉最大堆

从 2D 矩阵构建链表

鸡尾酒排序

使用 Hoare 分区法的快速排序

N 元树中给定节点的兄弟数量

在行和列排序的矩阵中搜索

双端优先队列

蚁群优化导论

AVL 树的平衡因子是什么

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器