平衡二分木リートコードソリューション


難易度 簡単に
よく聞かれる Amazon (アマゾン) Google マイクロソフト
配列

A 二分木 ツリー内のすべてのノードの左右のサブツリーの高さの差が最大で1の場合、は高さのバランスが取れています。この問題では、バランスの取れた二分木をチェックします。

平衡二分木リートコードソリューション

             2
        
          / 
    
        1

      /
 
    4
Not balanced
     1

  /     \

2         3
Balanced

アプローチ

それを考えるのは直感的です あらゆる 二分木のノードでは、左右のサブツリーが必要な条件を満たしているかどうかを確認できます。 それは "強引な" 方法。

しかし、ツリーのバランスが取れているかどうかを確認するために、次の理由でアプローチを改善することができます。 時間と空間 複雑さ。

私たちは、問題を解決するようなアプローチに従います。 ボトムアップ マナー。 ノードのサブツリー自体がバランスの取れたバイナリであるかどうかを確認します (か否か)同時に二分木の高さを取得します。これは再帰を使用して一般化できます。

アルゴリズム(ブルートフォース)

  1. ルートから開始し、バイナリツリーをトラバースし続けます。 ルート になる NULL
  2. を使用して左右のサブツリーの高さを取得します 高さ() function
    • 差が '1':
      • falseを返します。 木がバランス条件を満たしていないので
    • 左右のサブツリーのバランス状態を再帰的にチェックします
  3. 結果を印刷する

アルゴリズム(最適)

  1. 木が 空の、バランスが取れていると言えます。 そうでない場合は、他の手順に従うことができます。
  2. 「ヘルパー関数を作成して、「高さ再帰を使用して、現在のサブツリーの」。
  3. 高さ関数は次を返します:
    • -1、それが不均衡な木である場合
    • それ以外の場合は高さ。
  4. サブツリーに左または右のサブツリーがある場合 アンバランス または、高さが「1」を超えて異なる場合は、-1を返します。
  5. それ以外の場合は、このサブツリーの高さを次のように返します。 1 + max(left_height、right_height)

製品の導入

平衡二分木リートコードソリューションのC ++プログラム

ブルートフォース法

#include <bits/stdc++.h>
using namespace std;
struct treeNode
{
    int value;
    treeNode *left , *right;
    treeNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};


int height(treeNode* root)
{
    if(root == NULL)
        return 0;
    return max(height(root->left) , height(root->right)) + 1;
}


bool balanced(treeNode* root)
{
    if(root == NULL)
    return true;

    int l = height(root->left) , r = height(root->right);
    //calling height function at every node
    if(abs(l - r) > 1)
        return false;

    return balanced(root->left) && balanced(root->right);
}


int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(2);
    root->left->left = new treeNode(4);
    
    if(balanced(root))
        cout << "Balanced" << '\n';
    else
        cout << "Not Balanced" << '\n';
    return 0;
}

最適な方法

#include <bits/stdc++.h>
using namespace std;
struct treeNode
{
    int value;
    treeNode *left , *right;
    treeNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};


int height(treeNode* root)
{
    if(root == NULL)
        return 0;
    int l = height(root->left);
    int r = height(root->right);
    if(l == -1 || r == -1 || abs(l - r) > 1)
        return -1;
    return max(l , r) + 1;
}


bool balanced(treeNode* root)
{
    if(root == NULL)
        return true;

    return (height(root) != -1);
}


int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(2);
    root->left->left = new treeNode(4);

    if(balanced(root))
        cout << "Balanced" << '\n';
    else
        cout << "Not Balanced" << '\n';
    return 0;
}
Not Balanced

平衡二分木リートコードソリューションのJavaプログラム

強引な

import java.lang.Math;

class treeNode
{
    int value;
    treeNode left, right;

    public treeNode(int x)
    {
        value= x;
        left = right = null;
    }
}

class balanced_binary_tree
{
    public static int height(treeNode root)
    {
        if(root == null)
            return 0;
        return Math.max(height(root.left) , height(root.right)) + 1;
    }


    public static boolean balanced(treeNode root)
    {
        if(root == null)
            return true;

        int l = height(root.left) , r = height(root.right);
        if(Math.abs(r - l) > 1)
            return false;
        return balanced(root.left) && balanced(root.right);
    }


    public static void main(String args[])
    {
        treeNode root = new treeNode(2);
        root.left = new treeNode(1);
        root.right = new treeNode(3);

        if(balanced(root))
            System.out.println("Balanced");
        else
            System.out.println("Not Balanced");
    }
}

最適な方法

import java.lang.Math;

class treeNode
{
    int value;
    treeNode left, right;

    public treeNode(int x)
    {
        value= x;
        left = right = null;
    }
}

class balanced_binary_tree
{
    public static int height(treeNode root)
    {
        if(root == null)
            return 0;

        int l = height(root.left);
        int r = height(root.right);

        if(l == -1 || r == -1 || Math.abs(l - r) > 1)
            return -1;

        return Math.max(l , r) + 1;
    }


    public static boolean balanced(treeNode root)
    {
        if(root == null)
            return true;

        return (height(root) != -1);
    }


    public static void main(String args[])
    {
        treeNode root = new treeNode(2);
        root.left = new treeNode(1);
        root.left.left = new treeNode(4);

        if(balanced(root))
            System.out.println("Balanced");
        else
            System.out.println("Not Balanced");
    }
}
Not Balanced

平衡二分木リートコードソリューションの複雑さの分析

時間の複雑さ

ブルートフォース法の時間計算量は O(N * N)、最悪の場合(歪んだ木)。 ただし、最適なアプローチは オン) シングルパスのみを行うための時間。

スペースの複雑さ

再帰は補助スタックスペースを使用するため、どちらの場合もO(N)。