Are you sure you want to delete the question?

If your question is resolved, you may close it.

Leaving a resolved question undeleted may help others!

We hope you find it useful!

leetcode 2385についてstartノードが二つの場合

解決したいこと

leetcode 2385
https://leetcode.com/problems/amount-of-time-for-binary-tree-to-be-infected/
の問題について

リンクの問題ではstartノードは一つしか与えられていませんが、仮にstart1,start2と二つ与えられた場合の解決策

input例

//input
13
1 5 3 -1 4 10 6 9 2 -1 -1 -1 -1
3 5

//output
2

//tree
               1  
            /     \
           5       3
            \     / \
             4   10  6
            / \ 
           9   2


//説明
0回目:3 5
1回目:1 4 10 6
2回目:9 2

//input
3
1 2 -1
1 2

//output
0

//tree
             1  
            /     
           2      

//説明
0回目:1 2
 

ノードが一つの場合は何とか理解できましたが、二つになるとstart1とstart2の関係がどうしてもつかめません。
問題の制限はノードが一つの場合とあまり変わりません

0

1Answer

それぞれのスタート地点からの感染を合成すればよいと思います。

つまり例でいえば③をスタート地点とした結果

  • Minute 0: 3
  • Minute 1: 1, 6, 10
  • Minute 2: 5
  • Minute 3: 4
  • Minute 4: 2, 9

と⑤をスタート地点とした結果

  • Minute 0: 5
  • Minute 1: 1, 4
  • Minute 2: 2, 3, 9
  • Minute 3: 6, 10

を合わせて

  • Minute 0: 3, 5
  • Minute 1: 1, 4, 6, 10
  • Minute 2: 2, 3, 5, 9
  • Minute 3: 4, 6, 10
  • Minute 4: 2, 9

として各ノードが先に (もしくは同時に) 感染していた分を除去すれば

  • Minute 0: 3, 5
  • Minute 1: 1, 4, 6, 10
  • Minute 2: 2, 9

という結果になります。

ここではわかりやすさのためそれぞれで完了させてから合成という説明をしましたが同時並行でも出来るはずです。

追記

プログラムを書いてみました。 C++17 を想定しています。

入出力が面倒だったので例示されている問題を最初から配列の形でプログラムに埋め込んでますし、感染がわかった時点で個々に出力していて感染タイミングごとにまとめてません。 とりあえず感染を幅優先探索のようにキュー構造を使って表すという考え方がわかる程度に雑にまとめたものです。

#include <iostream>
#include <queue>
#include <vector>

using number = unsigned long int;

struct node {
    const number parent;
    const number left;
    const number right;
    bool infected;
    node(number parent, number left, number right) : parent(parent), left(left), right(right), infected(false) {}
};

struct entry {
    const number node_number;
    const number step;
    entry(number node_number, number step) : node_number(node_number), step(step) {}
};

std::ostream& operator<<(std::ostream& os, const entry& e) {
    os << "node " << e.node_number << " is infect at minute " << e.step;
    return os;
};

int main(void) {
    // 対象となる二分木。
    // 各要素はそれに接続されている親ノード、左の子、右の子の番号を持つ。
    // 0 は終端を表している。
    std::vector<node> tree = {
        {0, 0, 0},   // 0 番目ノードは使わないので適当に埋める
        {0, 5, 3},   // 1 番目ノード
        {4, 0, 0},   // 2 番目ノード
        {1, 10, 6},  // 3 番目ノード
        {5, 9, 2},   // 4 番目ノード
        {1, 0, 4},   // 5 番目ノード
        {3, 0, 0},   // 6 番目ノード
        {0, 0, 0},   //  7 番目ノードは使わないので適当に埋める
        {0, 0, 0},   //  8 番目ノードは使わないので適当に埋める
        {4, 0, 0},   //  9 番目ノード
        {3, 0, 0},   //  10 番目ノード
    };

    // 最初の予定としてスタート地点を入れる
    std::queue<entry> schedule;
    schedule.emplace(3, 0);
    schedule.emplace(5, 0);

    while (! schedule.empty()) {
        auto task = schedule.front();
        schedule.pop();
        if (auto& cursor = tree.at(task.node_number); cursor.infected == false) {
            std::cout << task << std::endl;
            cursor.infected = true;
            if (cursor.parent) schedule.emplace(cursor.parent, task.step + 1);
            if (cursor.left) schedule.emplace(cursor.left, task.step + 1);
            if (cursor.right) schedule.emplace(cursor.right, task.step + 1);
        }
    }
};
1Like

Comments

  1. ご回答ありがとうございます!
    なるほどですね。
    ただ、コードで再現するとまた色々考慮しなければならないので、ちょっと考えてみます。
    アイディアありがとうございました!

Your answer might help someone💌