二叉树到二叉搜索树的转换


难度级别 易得奖学金
经常问 土砖 亚马逊 Apple 彭博 谷歌 微软 VMware的
二进制搜索树 二叉树 深度优先搜索 树遍历

在二叉树到二叉搜索树的转换问题中,我们给出了将二叉树转换为二叉搜索树的方法,而无需更改其结构。 .

使用案列

输入

二叉树到二叉搜索树的转换

输出

二叉树到二叉搜索树的转换

预购:13 8 6 47 25 51

算法

我们不必更改二叉树的结构并将其转换为二叉搜索树。 注意按顺序排列的Binary Search Tree的属性 遍历 二叉搜索树的结果导致排序后的数据。 我们将使用此属性来实现所需的结果。

这个想法是将二叉树的有序遍历存储到一个 排列,对数组进行排序,然后遍历数组和二叉树(以有序形式),并将二叉树中的每个节点替换为数组中的相应元素。 这会将Binary Tree转换为Binary Search Tree。

  1. 创建一个名为inOrder的数组。
  2. 以顺序形式遍历给定的二叉树,并将节点的值存储在数组“ inOrder”中。
  3. 对数组进行排序。
  4. 同时遍历数组和二叉树,并用inOrder数组中的值替换二叉树中相应节点的值。
  5. 二叉树被转换为二叉搜索树。

时间复杂度= O(n log(n))
空间复杂度= O(n),因为我们使用数组存储有序遍历
其中n是给定二叉树中节点的数量。

说明

考虑上面示例中显示的二叉树。

步骤1和2

将二叉树的有序遍历存储在数组中。
inOrder [] = {47,51,25,6,13,8}

步骤

对数组进行排序。
inOrder = {6,8,13,25,47,51}

步骤

同时遍历数组和二叉树,并用已排序的inOrder数组的相应元素替换二叉树的元素。
二叉树现在看起来像

二叉树被转换为二叉搜索树。

二叉树到二叉搜索树转换的JAVA代码

import java.util.ArrayList;
import java.util.Collections;

public class BinaryTreeToBinarySearchTreeConversion {
    // class representing Node of a Binary Tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    // class to provide a wrapper around index
    // so that we can pass it by reference
    static class Index {
        int index;

        public Index(int index) {
            this.index = index;
        }
    }

    // function to print pre order traversal of a binary tree
    private static void preOrder(Node root) {
        if (root != null) {
            System.out.print(root.data + " ");
            preOrder(root.left);
            preOrder(root.right);
        }
    }

    // function to traverse in binary tree in in-order form and store the elements
    // in a list
    private static void inOrderAndFormList(Node root, ArrayList<Integer> inorder) {
        if (root != null) {
            inOrderAndFormList(root.left, inorder);
            // store the current value in the list
            inorder.add(root.data);
            inOrderAndFormList(root.right, inorder);
        }
    }

    // function to traverse in binary tree in in-order form and
    // change the value of elements accordingly
    private static void inOrderAndChange(Node root, ArrayList<Integer> inOrder, Index index) {
        if (root != null) {
            inOrderAndChange(root.left, inOrder, index);
            // change the current element of Tree with current element of list
            root.data = inOrder.get(index.index);
            // increment index by 1
            index.index++;
            inOrderAndChange(root.right, inOrder, index);
        }
    }

    private static void convertToBST(Node root) {
        // create a list and store the inorder of the given Binary Tree
        ArrayList<Integer> inOrder = new ArrayList<>();
        inOrderAndFormList(root, inOrder);

        // Sort the list
        Collections.sort(inOrder);

        // traverse in binary tree and list simultaneously and change the required values
        inOrderAndChange(root, inOrder, new Index(0));
    }

    public static void main(String[] args) {
        // Example Tree
        Node root = new Node(25);
        root.left = new Node(51);
        root.right = new Node(13);
        root.left.left = new Node(47);
        root.right.left = new Node(6);
        root.right.right = new Node(8);

        convertToBST(root);

        preOrder(root);
        System.out.println();
    }
}
13 8 6 47 25 51

二叉树到二叉搜索树转换的C ++代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// class representing Node of a Binary Tree
class Node {
    public:
    int data;
    Node *left;
    Node *right;
    
    Node(int d) {
        data = d;
    }
};

// global variable index
int index = 0;

void preOrder(Node *root) {
    if (root != NULL) {
        cout<<root->data<<" ";
        preOrder(root->left);
        preOrder(root->right);
    }
}

// function to traverse in binary tree in in-order form and store the elements
// in a list
void inOrderAndFormList(Node *root, vector<int> &inOrder) {
    if (root != NULL) {
        inOrderAndFormList(root->left, inOrder);
        // store the current value in the list
        inOrder.push_back(root->data);
        inOrderAndFormList(root->right, inOrder);
    }
}

// function to traverse in binary tree in in-order form and
// change the value of elements accordingly
void inOrderAndChange(Node *root, vector<int>& inOrder) {
    if (root != NULL) {
        inOrderAndChange(root->left, inOrder);
        
        // change the current element of Tree with current element of list
        root->data = inOrder[index];
        index++;
        
        inOrderAndChange(root->right, inOrder);
    }
}

void convertToBST(Node *root) {
    // create a list and store the inorder of the given Binary Tree
    vector<int> inOrder;
    inOrderAndFormList(root, inOrder);

    // Sort the list
    sort(inOrder.begin(), inOrder.end());

    // traverse in binary tree and list simultaneously and change the required values
    index = 0;
    inOrderAndChange(root, inOrder);
}

int main() {
    // Example Tree
    Node *root = new Node(25);
    root->left = new Node(51);
    root->right = new Node(13);
    root->left->left = new Node(47);
    root->right->left = new Node(6);
    root->right->right = new Node(8);

    convertToBST(root);

    preOrder(root);
    cout<<endl;
    
    return 0;
}
13 8 6 47 25 51

參考資料