將正常的BST轉換為平衡的BST  


難度級別 中烘焙
經常問 美國運通卡 ByteDance 第一資本 雜貨店 英特爾 Splunk的 百會
二進制搜索樹 二叉樹

問題陳述  

給定二進制搜索樹(BST),編寫將BST轉換為平衡二進制搜索樹的算法。 平衡的二叉搜索樹不過是二叉搜索樹,其左子樹和右子樹的高度之差小於或等於1。

範例檔案  

輸入

將正常的BST轉換為平衡的BST

產量

將正常的BST轉換為平衡的BST

預購:31 17 3 23 48 45 50 62

輸入

將正常的BST轉換為平衡的BST

產量

將正常的BST轉換為平衡的BST

預購:8 7 9

 

將普通BST轉換為平衡BST的算法  

一種方法是按順序遍歷給定的二叉搜索樹,並將元素存儲在自平衡樹中,例如 AVL樹 或一棵紅黑樹。 這種方法效率不高,它花費O(N log N)時間並使用O(N)額外空間。

給定的問題類似於從排序的數組構建平衡的二進制搜索樹,並且我們知道如何將排序的數組或列表轉換為平衡的二進制搜索樹。 如果我們仔細研究給定的問題,可以將問題轉換為從排序的數組構造平衡的二進制搜索樹。

想法是按順序遍歷給定的BST,並將節點存儲在數組中。 數組將按排序順序包含數據。 然後我們將排序後的數組轉換為平衡數組 二叉搜索樹.

1. Traverse the given binary search tree in in-order traversal and store the nodes in an array, let the array be inOrderNodes.
2. The middle element of the array forms the root of the balanced BST and all the elements to the left of middle element forms the left sub-tree and all the elements to the right of middle element forms the right sub-tree.
3. Make root's left as the result of a recursive call for step 2. For left sub-tree the start index is start in step 2 and end index is mid - 1.
4. Make root's right as the result of a recursive call for step 2. For right sub-tree the start index is mid + 1 and end index is end in step 2.
5. Return root.

複雜度分析  

時間複雜度 = 上), 因為我們遍歷了整棵樹 節點。 對於此算法,我們具有線性時間複雜度。
空間複雜度 = 上), 因為我們使用的是大小數組 n 用於存儲二進制搜索樹的有序遍歷。
其中,n是給定的二進制搜索樹中的節點數。

也可以看看
查找二叉樹的兩個節點之間的距離

JAVA代碼,用於將普通BST轉換為平衡BST  

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

import java.util.ArrayList;
class ConvertANormalBSTToBalancedBST {
    // class representing node of a binary tree
    static class Node {
        int data;
        Node left, right;
        public Node(int data) {
            this.data = data;
        }
    }
    // 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 store the in-order traversal of a binary tree to an array
    private static void storeInOrderTraversal(Node root, ArrayList<Integer> inOrderNodes) {
        if (root != null) {
            storeInOrderTraversal(root.left, inOrderNodes);
            inOrderNodes.add(root.data);
            storeInOrderTraversal(root.right, inOrderNodes);
        }
    }
    private static Node convertSortedArrayToBalancedBST(ArrayList<Integer> inOrderNodes, int start, int end) {
        // Base Case
        if (start > end) {
            return null;
        }
        // middle element of the array forms the node
        int mid = (start + end) / 2;
        Node root = new Node(inOrderNodes.get(mid));
        // elements to the left of middle element forms left subtree
        root.left = convertSortedArrayToBalancedBST(inOrderNodes, start, mid - 1);
        // elements to the right of middle element forms right subtree
        root.right = convertSortedArrayToBalancedBST(inOrderNodes, mid + 1, end);
        // return root
        return root;
    }
    private static Node convertToBalancedBST(Node root) {
        // create an array
        ArrayList<Integer> inOrderNodes = new ArrayList<>();
        // store the in-order traversal in the array
        storeInOrderTraversal(root, inOrderNodes);
        // make balanced BST from sorted array
        return convertSortedArrayToBalancedBST(inOrderNodes, 0, inOrderNodes.size() - 1);
    }
    public static void main(String[] args) {
        // Example 1
        Node root1 = new Node(50);
        root1.left = new Node(23);
        root1.right = new Node(62);
        root1.left.left = new Node(17);
        root1.left.right = new Node(45);
        root1.left.left.left = new Node(3);
        root1.left.right.left = new Node(31);
        root1.left.right.right = new Node(48);
        root1 = convertToBalancedBST(root1);
        preOrder(root1);
        System.out.println();
        // Example 2
        Node root2 = new Node(7);
        root2.right = new Node(8);
        root2.right.right = new Node(9);
        root2 = convertToBalancedBST(root2);
        preOrder(root2);
        System.out.println();
    }
}
31 17 3 23 48 45 50 62 
8 7 9

用於將普通BST轉換為平衡BST的C ++代碼  

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

// class representing node of a binary tree 
class Node { 
    public: 
    int data; 
    Node *left; 
    Node *right; 
    
    Node(int d) { 
        data = d; 
        left = right = NULL; 
    } 
};

// function to print pre-order traversal of a binary tree
void preOrder(Node *root) {
    if (root != NULL) {
        cout<<root->data<<" ";
        preOrder(root->left);
        preOrder(root->right);
    }
}

// function to store the in-order traversal of a binary tree to an array
void storeInOrderTraversal(Node *root, vector<int> &inOrderNodes) {
    if (root != NULL) {
        storeInOrderTraversal(root->left, inOrderNodes);
        inOrderNodes.push_back(root->data);
        storeInOrderTraversal(root->right, inOrderNodes);
    }
}

Node* convertSortedArrayToBalancedBST(vector<int> &inOrderNodes, int start, int end) {
    // Base Case
    if (start > end) {
        return NULL;
    }
    
    // middle element of the array forms the node
    int mid = (start + end) / 2;
    Node *root = new Node(inOrderNodes[mid]);
    
    // elements to the left of middle element forms left subtree
    root->left = convertSortedArrayToBalancedBST(inOrderNodes, start, mid - 1);
    // elements to the right of middle element forms right subtree
    root->right = convertSortedArrayToBalancedBST(inOrderNodes, mid + 1, end);
    
    // return root
    return root;
}

Node* convertToBalancedBST(Node *root) {
    // create an array
    vector<int> inOrderNodes;
    // store the in-order traversal in the array
    storeInOrderTraversal(root, inOrderNodes);
    
    // make balanced BST from sorted array
    return convertSortedArrayToBalancedBST(inOrderNodes, 0, inOrderNodes.size() - 1);
}

int main() {
    // Example 1
    Node *root1 = new Node(50);
    root1->left = new Node(23);
    root1->right = new Node(62);
    root1->left->left = new Node(17);
    root1->left->right = new Node(45);
    root1->left->left->left = new Node(3);
    root1->left->right->left = new Node(31);
    root1->left->right->right = new Node(48);
    root1 = convertToBalancedBST(root1);
    preOrder(root1);
    cout<<endl;

    // Example 2
    Node *root2 = new Node(7);
    root2->right = new Node(8);
    root2->right->right = new Node(9);
    root2 = convertToBalancedBST(root2);
    preOrder(root2);
    cout<<endl;
    
    return 0;
}
31 17 3 23 48 45 50 62 
8 7 9