Мінімальная глыбіня развязання штрых-кода двайковага дрэва


Узровень складанасці Лёгка
Часта пытаюцца ў амазонка яблык facebook
Двайковае дрэва Шырыня Першы пошук Глыбіня Першы пошук

У гэтай задачы нам трэба знайсці даўжыню самага кароткага шляху ад кораня да любога ліста ў дадзеным бінарнае дрэва. Звярніце ўвагу, што «даўжыня шляху» тут азначае колькасць вузлоў ад каранёвага вузла да ліставога вузла. Гэтая даўжыня называецца мінімальнай глыбінёй бінарнага дрэва.

Прыклад

уваход

Мінімальная глыбіня развязання штрых-кода двайковага дрэва

 

 

 

 

 

 

 

2

Тлумачэнне

Самы кароткі шлях: 2 -> 1 , які мае даўжыню 2

уваход

 

 

 

 

 

 

 

3

Тлумачэнне

Самы кароткі шлях: 1 -> 2 -> 3, даўжынёй 3

Падыход (рэкурсіўны)

Гэтая праблема структурна такая ж, як і знайсці вышыню бінарнага дрэва, але ў гэтым выпадку нам трэба знайсці мінімальную вышыню / глыбіню паміж коранем і любым лістом дрэва. Мы можам атрымаць мінімальную глыбіню левага і правага дрэў кораня пры дапамозе Глыбіня першага пошуку (DFS) а потым вярнуць мінімум з дзвюх глыбінь. Нам трэба разгледзець некаторыя выпадкі, калі ёсць любое з левага і правага дрэў вузла NULL. Калі левае паддрэва ёсць NULL, ён верне вышыню, роўную але паколькі мы не знайшлі лісця ў гэтым паддрэве, дык і гэта будзе няправільным адказам. Такім чынам, нам трэба выклікаць рэкурсіўную функцыю толькі тады, калі вузел, на які яна выклікаецца, ёсць НЕ нулявы.

Алгарытм

  1. Стварыце функцыю minDepth () каб вярнуць мінімальную глыбіню пройдзенага кораня
  2. Калі корань ёсць NULL, вярнуцца 0
  3. У выпадку, калі абодва пакінуць і права паддрэвы ёсць NULL, вярнуцца 1
  4. Калі левае паддрэва ёсць NULL, вярнуцца 1 + мінГлыбіня (корань-> справа)
  5. У іншым выпадку правільнае паддрэва NULL, вярнуцца 1 + мінГлыбіня (корань-> злева)
  6. Вяртанне 1 + мінімум (мінглыбіня(корань-> злева), мінглыбіня(корань-> справа))

Рэалізацыя мінімальнай глыбіні рашэння двайковага дрэва Leetcode

Праграма 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 minDepth(treeNode* root)
{
    if(root == NULL)
        return 0;
    if(root->left == NULL && root->right == NULL)
        return 1;
    if(root->left == NULL)
        return 1 + minDepth(root->right);
    if(root->right == NULL)
        return 1 + minDepth(root->left);
    return 1 + min(minDepth(root->left) , minDepth(root->right));
}

int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(1);
    root->right = new treeNode(3);
    root->right->left = new treeNode(4);
    root->right->right = new treeNode(5);
    cout << minDepth(root) << '\n';
}

Праграма Java

import java.util.*;

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

class Pair
{
    treeNode key;
    int value;

    Pair(treeNode root , int val)
    {
        key = root;
        value = val;
    }
}

class Minimum_Depth_Of_A_Binary_Tree
{
    public static void main(String args[])
    {
        treeNode root = new treeNode(2);
        root.left = new treeNode(1);
        root.right = new treeNode(3);
        root.right.left = new treeNode(4);
        root.right.right = new treeNode(5);
        System.out.println(minDepth(root));
    }

    static int minDepth(treeNode root)
    {
        if(root == null)
            return 0;
        if(root.left == null && root.right == null)
            return 1;
        if(root.left == null)
            return 1 + minDepth(root.right);
        if(root.right == null)
            return 1 + minDepth(root.left);
        return 1 + Math.min(minDepth(root.left) , minDepth(root.right));

    }
}
2

Аналіз складанасці мінімальнай глыбіні развязання штрых-кода двайковага дрэва

Складанасць часу

O (N), бо мы перасякаем цэлае дрэва адзін раз, нават у горшым выпадку.

Касмічная складанасць

O (N). Калі двайковае дрэва перакошана, рэкурсіўныя кадры стэка могуць займаць да O (N) прасторы.

Падыход (ітэрацыйны)

Мы можам выкарыстоўваць Пошук па шырыні (BFS) каб знайсці першы вузел, які з'яўляецца лістом, і вярнуць яго глыбіню ад кораня. Мы можам выкарыстоўваць чаргу для захоўвання пары вузлоў і іх глыбіні ад каранёвага вузла. Калі мы атрымліваем вузел, які з'яўляецца лістом, мы вяртаем яго глыбіню.

Алгарытм

  1. Калі корань ёсць NULL, вярнуцца 0
  2. Ініцыялізаваць чаргу з пары дрэвавых вузлоў і цэлых лікаў
  3. Націсніце каранёвы вузел у чаргу з глыбінёй як 1
  4. Пакуль чарга не пустая:
    • Атрымаць глыбіню і адрас вузла элемента пярэдняй чаргі
    • Выдаліць элемент з чаргі
    • Калі пярэдні вузел ёсць NULL, вярнуць яго глыбіню
    • Націсніце пакінуць і права вузлы да дрэва, калі яны ёсць ня нуля
  5. Вяртаць -1 для падтрымання сінтаксісу праграмы, паколькі функцыя вяртае цэлае лік

Рэалізацыя мінімальнай глыбіні рашэння двайковага дрэва Leetcode

Праграма 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 minDepth(treeNode* root)
{
    if(root == NULL)
        return 0;
    queue < pair <treeNode* , int> > q;
    q.push({root , 1});

    treeNode* frontNode;
    int depth;

    while(!q.empty())
    {
        frontNode = q.front().first;
        depth = q.front().second;
        q.pop();

        if(frontNode->left == NULL && frontNode->right == NULL)
            return depth;

        if(frontNode->left != NULL)
            q.push({frontNode->left , depth + 1});

        if(frontNode->right != NULL)
            q.push({frontNode->right , depth + 1});
    }
    return -1;
}

int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(1);
    root->right = new treeNode(3);
    root->right->left = new treeNode(4);
    root->right->right = new treeNode(5);
    cout << minDepth(root) << '\n';
}


Праграма Java

import java.util.*;

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

class Pair
{
    treeNode key;
    int value;

    Pair(treeNode root , int val)
    {
        key = root;
        value = val;
    }
}

class Minimum_Depth_Of_A_Binary_Tree
{
    public static void main(String args[])
    {
        treeNode root = new treeNode(2);
        root.left = new treeNode(1);
        root.right = new treeNode(3);
        root.right.left = new treeNode(4);
        root.right.right = new treeNode(5);
        System.out.println(minDepth(root));
    }

    static int minDepth(treeNode root)
    {
        if(root == null)
            return 0;
        LinkedList <Pair> q = new LinkedList<>();
        q.add(new Pair(root , 1));

        treeNode frontNode;
        int depth;

        while(q.size() > 0)
        {
            frontNode = q.peek().key;
            depth = q.peek().value;

            q.remove();

            if(frontNode.left == null && frontNode.right == null)
                return depth;

            if(frontNode.left != null)
                q.add(new Pair(frontNode.left , depth + 1));

            if(frontNode.right != null)
                q.add(new Pair(frontNode.right , depth + 1));
        }
        return -1;
    }
}
2

Аналіз складанасці мінімальнай глыбіні развязання штрых-кода двайковага дрэва

Складанасць часу

O (N), калі мы яшчэ раз перабягаем усё дрэва.

Касмічная складанасць

O (N), паколькі мы выкарыстоўваем чаргу для захоўвання звестак пра кожны вузел.