1382. Balance a Binary Search Tree

leetcode medium

#csharp#leetcode#math#medium#recursion#search#sort#tree#two-pointers

Task

Дан корень бинарного дерева поиска. Верните сбалансированное бинарное дерево поиска с теми же значениями узлов. Если существует более одного ответа, верните любой из них.

Бинарное дерево поиска считается сбалансированным, если глубина двух поддеревьев каждого узла никогда не отличается более чем на 1.

Пример:

Input: root = [1,null,2,null,3,null,4,null,null]

Output: [2,1,3,null,null,null,4]

Explanation: This is not the only correct answer, [3,1,4,null,2] is also correct.

C# solution

matched/original

public class Solution {
    public TreeNode BalanceBST(TreeNode root) {
        if (root == null) return null;
        TreeNode vineHead = new TreeNode(0);
        vineHead.right = root;
        TreeNode current = vineHead;
        while (current.right != null) {
            if (current.right.left != null) {
                RightRotate(current, current.right);
            } else {
                current = current.right;
            }
        }
        int nodeCount = 0;
        current = vineHead.right;
        while (current != null) {
            nodeCount++;
            current = current.right;
        }
        int m = (int)Math.Pow(2, Math.Floor(Math.Log(nodeCount + 1) / Math.Log(2))) - 1;
        MakeRotations(vineHead, nodeCount - m);
        while (m > 1) {
            m /= 2;
            MakeRotations(vineHead, m);
        }
        TreeNode balancedRoot = vineHead.right;
        return balancedRoot;
    }
    private void RightRotate(TreeNode parent, TreeNode node) {
        TreeNode tmp = node.left;
        node.left = tmp.right;
        tmp.right = node;
        parent.right = tmp;
    }
    private void LeftRotate(TreeNode parent, TreeNode node) {
        TreeNode tmp = node.right;
        node.right = tmp.left;
        tmp.left = node;
        parent.right = tmp;
    }
    private void MakeRotations(TreeNode vineHead, int count) {
        TreeNode current = vineHead;
        for (int i = 0; i < count; i++) {
            TreeNode tmp = current.right;
            LeftRotate(current, tmp);
            current = current.right;
        }
    }
}

C++ solution

auto-draft, review before submit

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

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public TreeNode BalanceBST(TreeNode root) {
        if (root == null) return null;
        TreeNode vineHead = new TreeNode(0);
        vineHead.right = root;
        TreeNode current = vineHead;
        while (current.right != null) {
            if (current.right.left != null) {
                RightRotate(current, current.right);
            } else {
                current = current.right;
            }
        }
        int nodeCount = 0;
        current = vineHead.right;
        while (current != null) {
            nodeCount++;
            current = current.right;
        }
        int m = (int)Math.Pow(2, Math.Floor(Math.Log(nodeCount + 1) / Math.Log(2))) - 1;
        MakeRotations(vineHead, nodeCount - m);
        while (m > 1) {
            m /= 2;
            MakeRotations(vineHead, m);
        }
        TreeNode balancedRoot = vineHead.right;
        return balancedRoot;
    }
    private void RightRotate(TreeNode parent, TreeNode node) {
        TreeNode tmp = node.left;
        node.left = tmp.right;
        tmp.right = node;
        parent.right = tmp;
    }
    private void LeftRotate(TreeNode parent, TreeNode node) {
        TreeNode tmp = node.right;
        node.right = tmp.left;
        tmp.left = node;
        parent.right = tmp;
    }
    private void MakeRotations(TreeNode vineHead, int count) {
        TreeNode current = vineHead;
        for (int i = 0; i < count; i++) {
            TreeNode tmp = current.right;
            LeftRotate(current, tmp);
            current = current.right;
        }
    }
}

Java solution

matched/original

class Solution {
    public TreeNode balanceBST(TreeNode root) {
        if (root == null) return null;

        TreeNode vineHead = new TreeNode(0);
        vineHead.right = root;
        TreeNode current = vineHead;

        while (current.right != null) {
            if (current.right.left != null) {
                rightRotate(current, current.right);
            } else {
                current = current.right;
            }
        }

        int nodeCount = 0;
        current = vineHead.right;
        while (current != null) {
            nodeCount++;
            current = current.right;
        }

        int m = (int) Math.pow(2, Math.floor(Math.log(nodeCount + 1) / Math.log(2))) - 1;
        makeRotations(vineHead, nodeCount - m);
        while (m > 1) {
            m /= 2;
            makeRotations(vineHead, m);
        }

        TreeNode balancedRoot = vineHead.right;
        return balancedRoot;
    }

    private void rightRotate(TreeNode parent, TreeNode node) {
        TreeNode tmp = node.left;
        node.left = tmp.right;
        tmp.right = node;
        parent.right = tmp;
    }

    private void leftRotate(TreeNode parent, TreeNode node) {
        TreeNode tmp = node.right;
        node.right = tmp.left;
        tmp.left = node;
        parent.right = tmp;
    }

    private void makeRotations(TreeNode vineHead, int count) {
        TreeNode current = vineHead;
        for (int i = 0; i < count; i++) {
            TreeNode tmp = current.right;
            leftRotate(current, tmp);
            current = current.right;
        }
    }
}

JavaScript solution

matched/original

var balanceBST = function(root) {
    if (!root) return null;

    const vineHead = new TreeNode(0);
    vineHead.right = root;
    let current = vineHead;

    while (current.right) {
        if (current.right.left) {
            rightRotate(current, current.right);
        } else {
            current = current.right;
        }
    }

    let nodeCount = 0;
    current = vineHead.right;
    while (current) {
        nodeCount++;
        current = current.right;
    }

    let m = 2 ** Math.floor(Math.log2(nodeCount + 1)) - 1;
    makeRotations(vineHead, nodeCount - m);
    while (m > 1) {
        m = Math.floor(m / 2);
        makeRotations(vineHead, m);
    }

    return vineHead.right;
};

function rightRotate(parent, node) {
    const tmp = node.left;
    node.left = tmp.right;
    tmp.right = node;
    parent.right = tmp;
}

function leftRotate(parent, node) {
    const tmp = node.right;
    node.right = tmp.left;
    tmp.left = node;
    parent.right = tmp;
}

function makeRotations(vineHead, count) {
    let current = vineHead;
    for (let i = 0; i < count; i++) {
        const tmp = current.right;
        leftRotate(current, tmp);
        current = current.right;
    }
}

Explanation

Algorithm

1⃣Инициализация. Создайте пустой список inorder для хранения значений узлов после обхода в порядке возрастания.

2⃣Выполнение обхода в порядке возрастания. Обойдите бинарное дерево поиска (BST) и заполните список inorder значениями узлов в отсортированном порядке.

3⃣Перестроение сбалансированного BST. Определите рекурсивную функцию createBalancedBST, которая принимает список inorder, начальный индекс и конечный индекс в качестве параметров. Если начальный индекс больше конечного, верните null (или эквивалент). Вычислите средний индекс как середину текущего диапазона. Создайте новый узел дерева со значением в среднем индексе. Рекурсивно создайте левое поддерево, используя левую половину текущего диапазона. Рекурсивно создайте правое поддерево, используя правую половину текущего диапазона. Верните корень вновь построенного сбалансированного BST.

😎