မှတ်ချက် – ဒီ Post သည် Algorithm Interview Preparation အပိုင်းဆက်ဖြစ်သည်။

ဒီနေ့ကျနော်တို့ solve မယ့် problem က Amount of Time for Binary Tree to Be Infected ပါ။ မေးခွန်းကို ဒီ link မှာသွားကြည့်ပါ။

ဒီမေးခွန်းကိုဖြေနိုင်ဖို့သိရမယ့်ဟာ ၂ ခုရှိတယ်။ တခုက Binary Tree ဆိုတာဘာလဲသိရမယ်။ နောက်တခုက Infection Spread ဆိုတဲ့ concept သိရမယ်။

Binary Tree ကတော့ရှင်းပါတယ်။ သူက tree, သူ့ရဲ့ node တွေကအများဆုံး children ၂ခုရှိမယ်။ left/rgith child ဆိုပီးပြောကြတယ်။ ဟိုးအပေါ်ဆုံးကကောင်ကိုကြ root node လို့ခေါ်တယ်။ အောက်ကကောင်ကြတော့ child node ပေါ့။ အဲ့ child node အောက်မှာလဲ children တွေရှိတယ်။

Infection Spread ဆိုတာက node တခုကရောဂါဖြစ်တာ သူ့နဲ့ဆက်ဆက်နေတဲ့ node တွေကိုကူးသွားတာ။ ဥပမာအလယ်မှာရှိတဲ့ node ဆိုရင် parent ကိုကူးမယ် left/right child ကိုကူးမယ်ဒါမျိုးပေါ့။ မေးခွန်းမှာမေးထားတာက Node တခုကိုကူးတာက ၁ မိနစ်ကြာမယ်ဆိုရင် tree ထဲမှာရှိတဲ့ node အကုန်လုံးကိုကူးသွားမယ့်အချိန်ဘယ်လောက်ကြာမလဲတဲ့။

အဲ့တော့ဒီပြဿနာကိုရှင်းဖို့ဆိုရင်ကျနော်တို့က tree ကို grpah ပြောင်းရမယ်။ graph ကိုမှ adjacency list ပြောင်းရမယ်။ ဒါမှကျနော်တို့က BFS လိုမျိုးသုံးပီးတော့ ရောဂါဖြစ်တဲ့နေရာကနေအကုန်လုံးကိုကူးတာရှာလို့ရမှာကိုး။

Graph အကြောင်းသေချာသိချင်ရင် ကျနော် ဒီမှာ ရေးထားတာဖတ်ကြည့်ရင်ပိုပီးရှင်းသွားမယ်။ 100 seconds နှင့်ရှင်းပြထားတာကိုဒီမှာကြည့်လို့ရတယ်။

ကျနော်နဲနဲလေး recap ပြန်လုပ်လိုက်မယ်။ ကျနော်တို့ကိုပေးမှာက binary tree။ ရောဂါကအလယ်ပိုင်းလောက်ကလဲဖြစ်နိုင်တယ်။ အဲ့တော့အကုန်ကူးတာကိုရှာဖို့ရာအတွက် adjacency list ပြောင်းပီးတော့ဖြစ်တဲ့နေရာကနေအကုန်လုံးကူးတာကို။ BFS နှင့်ရှာမယ်။

---

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} start
 * @return {number}
 */
var amountOfTime = function(root, start) {
    
};

ပထမဆုံးကျနော်တို့ buildGraph ဆိုပီး function အသစ်တခုရေးမယ်။

function buildGraph(node, graph, parent=null) {
    if(!node) return;
    
    if(!graph[node.val]) {
        graph[node.val] = []
    }

    if(parent) {
        graph[node.val].push(parent.val);
        graph[parent.val].push(node.val)
    }

    buildGraph(node.left, graph, node);
    buildGraph(node.right, graph, node);
}

ဘာလုပ်လိုက်တာလဲဆိုရင် binary tree ကို graph ပြောင်းလိုက်တာပေါ့။ သေချာမမြင်မှာစိုးလို့အောက်မှာနည်းနည်းထက်ရှင်းပြမယ်။

ထားပါတော့ကျနော်တို့ binary tree ကအောက်ကလိုမျိုးဆိုရင်

    1
   / \
  2   3

function TreeNode(val, left, right) {
    this.val = (val === undefined ? 0 : val);
    this.left = (left === undefined ? null : left);
    this.right = (right === undefined ? null : right);
}

TreeNode နှင့် tree လုပ်လိုက်မယ်ဆိုရင်။

let node1 = new TreeNode(1);
let node2 = new TreeNode(2);
let node3 = new TreeNode(3);

// connect nodes
node1.left = node2
node1.right = node3

အဲ့ဒီ့ tree ကိုကျနော်တို့ graph ပြောင်းမယ်ဆို

let graph = {};
buildGraph(node1, graph);

အောက်က graph result ရမယ်။

{
    "1": [
        2,
        3
    ],
    "2": [
        1
    ],
    "3": [
        1
    ]
}

ဒါဆိုရင်ကျနော်တို့ binary tree ရယ်။ နောက် binary tree ကနေ graph ကိုပြောင်းတာရယ်လောက်ပီထင်တယ်။

---

ကျနော်တို့လိုချင်တာရပီဖြစ်တဲ့အတွက် ပြဿနာရှင်းပါ့မယ်။

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} start
 * @return {number}
 */
var amountOfTime = function(root, start) {
    let graph = {}
    buildGraph(root, graph);

    let queue = [start];
    let seen = new Set(queue);
    let minutes = 0;

    while(queue.length > 0) {
        let size = queue.length;
        let spread = false;

        for(let i=0; i < size; i++) {
            let node = queue.shift();
            for(let neighbor of graph[node]) {
                if(!seen.has(neighbor)) {
                    spread = true;
                    seen.add(neighbor);
                    queue.push(neighbor);
                }
            }
        }

        if (spread) {
            minutes++;
        }
    }

    return minutes;
};

function buildGraph(node, graph, parent=null) {
    if(!node) return;
    
    if(!graph[node.val]) {
        graph[node.val] = []
    }

    if(parent) {
        graph[node.val].push(parent.val);
        graph[parent.val].push(node.val)
    }

    buildGraph(node.left, graph, node);
    buildGraph(node.right, graph, node);
}

အဲ့တော့ ကျနော်တို့ buildGraph လဲ implement လုပ်ခဲ့ပီ။ TreeNode ကတော့သူတို့ပြင်ဆင်ပေးမယ်ဆိုပီးအပေါ်မှာ comment နှင့်ဒါမျိုးလာမယ်ဆိုပီးပြထားတယ်။ အဆင်သင့်ယူသုံးလိုက်ရုံဘဲ။

BFS implementation ကိုကျနော်တို့ time tracking ထည့်ပေးလိုက်တယ်။ BFS ဖြစ်တဲ့အတွက် queue သုံးတယ်။ အဲ့တော့ကျနော်တို့ recursive သုံးလို့မရဘူး။ သူ့ BFS implemention ကိုသေချာ Graph မှာရှင်းပြထားတယ်။ ဒီလောက်ဆိုဘယ်လိုရှင်းရမလဲ ဘယ်လိုမျိုးဟာတွေသိထားဖို့လိုလဲဆိုတာသိလောက်ပီထင်ပါတယ်။