使用STL集將二叉樹轉換為二叉搜索樹


難度級別
經常問 亞馬遜 Coursera 谷歌 確實 Microsoft微軟 OYO房間
二進制搜索樹 二叉樹

問題陳述

我們得到一個 二叉樹 我們需要將其轉換為 二叉搜索樹。 問題“使用STL集進行從二叉樹到二進制搜索樹的轉換”要求使用STL集進行轉換。 我們已經討論過 將二叉樹轉換為BST 但是我們沒有討論使用Set的轉換。 轉換時,需要檢查的一件事是原始樹結構必須保持不變。

輸入

產量

使用STL集將二叉樹轉換為二叉搜索樹

 

使用Set將二叉樹轉換為BST的方法

我們已經討論過將二叉樹轉換為二叉樹的方法,但是這裡我們將使用內置的STL集。 因此,方法之一可能是首先構造一個平衡的二分搜索樹 AVL樹或紅黑 樹。 然後,我們對新創建的樹進行有序遍歷,並以類似的有序方式將內容複製回原始樹。

上面討論的方法要求創建不必要的自平衡二叉樹。 因此,為避免這種情況,我們討論了一種基於陣列的方法。 在這種方法中,我們首先進行了 遍歷 三個中的一個,然後對數組進行排序。 再次使用順序遍歷,我們替換了初始樹中的元素。

在這種方法中,我們將不會創建數組然後對其進行排序。 我們將使用使元素保持排序方式的集合。 因此,我們將遍歷樹並繼續將元素插入到 Wi-Fi:。 之後,我們將替換給定樹中的元素。

推薦碼

C ++代碼使用Set將二進制樹轉換為BST

#include <bits/stdc++.h>
using namespace std;

// defines the structure of a tree node
struct node{
    int data;
    node* left;
    node* right;
};

// inserts the given tree elements into the set
void insertIntoSet(node* root, set<int> &treeSet){
    if(root){
        insertIntoSet(root->left, treeSet);
        treeSet.insert(root->data);
        insertIntoSet(root->right, treeSet);
    }
}

// replace the elements of the initial tree
// with elements in treeSet in in-order fashion
void modifyBinaryTreeIntoBST(node* root, set<int> &treeSet)
{
    if(root){
        modifyBinaryTreeIntoBST(root->left, treeSet);
        root->data = *(treeSet.begin());
        treeSet.erase(treeSet.begin());
        modifyBinaryTreeIntoBST(root->right, treeSet);
    }
}

// Converts Binary tree to BST
void binaryTreeToBST(node* root)
{
    set<int> treeSet;
    // first fill the set
    insertIntoSet(root, treeSet);
    // then replace the elements in initial tree
    modifyBinaryTreeIntoBST(root, treeSet);
}

// creates and returns a new node with supplied node value
node* create(int data){
    node *tmp = new node();
    tmp->data = data;
    tmp->left = tmp->right = NULL;
    return tmp;
}

// simple in-order traversal
void inorder(node *root){
    if(root){
        inorder(root->left);
        cout<<root->data;
        inorder(root->right);
    }
}

int main()
{
    // constructing a binary tree
    // same as shown above
    node *root = create(1);
    root->right = create(2);
    root->right->left = create(4);
    root->right->left->left = create(5);
    root->right->left->right = create(3);

    cout<<"Inorder Traversal of given binary tree"<<endl;
    inorder(root);cout<<endl;
    binaryTreeToBST(root);
    cout<<"Inorder Traversal of modified tree\n";
    inorder(root);
}
Inorder Traversal of given binary tree
15432
Inorder Traversal of modified tree
12345

Java代碼使用Set將二進制樹轉換為BST

import java.util.*;
import java.lang.*;
import java.io.*;
 
class node{
  int data;
  node left;
  node right;
}
 
class Tree{
  // creates and returns a new node with supplied node value
  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = null;
    tmp.right = null;
    return tmp;
  }

  // inserts the given tree elements into the set
  static void insertIntoSet(node root, TreeSet<Integer> treeSet){
    if(root != null){
      insertIntoSet(root.left, treeSet);
      treeSet.add(root.data);
      insertIntoSet(root.right, treeSet);
    }
  }

  // replace the elements of the initial tree
  // with elements in treeSet in in-order fashion
  static void modifyBinaryTreeIntoBST(node root, TreeSet<Integer> treeSet)
  {
    if(root != null){
      modifyBinaryTreeIntoBST(root.left, treeSet);
      root.data = treeSet.pollFirst();
      modifyBinaryTreeIntoBST(root.right, treeSet);
    }
  }

  // Converts Binary tree to BST
  static void binaryTreeToBST(node root)
  {
    TreeSet<Integer> treeSet = new TreeSet<>();
    // first fill the set
    insertIntoSet(root, treeSet);
    // then replace the elements in initial tree
    modifyBinaryTreeIntoBST(root, treeSet);
  }

  // simple in-order traversal
  static void inorder(node root){
    if(root != null){
      inorder(root.left);
      System.out.print(root.data);
      inorder(root.right);
    }
  }

  public static void main(String[] args)
  {
    // constructing a binary tree
    // same as shown above
    node root = create(1);
    root.right = create(2);
    root.right.left = create(4);
    root.right.left.left = create(5);
    root.right.left.right = create(3);

    System.out.println("Inorder Traversal of given binary tree");
    inorder(root);
    System.out.println();
    binaryTreeToBST(root);
    System.out.println("Inorder Traversal of modified tree");
    inorder(root);
  }
}
Inorder Traversal of given binary tree
15432
Inorder Traversal of modified tree
12345

複雜度分析

時間複雜度

O(N log N),  其中N是樹中元素的數量。 在這裡,對數因子是由於集合的緣故而來的。 設置數據結構需要N倍的時間才能插入,搜索和刪除元素。

空間複雜度

上),這裡我們已經使用了額外的空間來存儲集合中的節點。 因此,用於轉換的算法本身俱有線性空間複雜度,並且整個程序也具有線性空間複雜度。