Binary Preach ၏ဆင်ခြေလျှောကိုမည်သို့တွက်ချက်ရမည်နည်း - PHP အကောင်အထည်ဖော်မှုခွဲခြမ်းစိတ်ဖြာမှု

Binary Tree ခြုံငုံသုံးသပ်ချက်

တစ် ဦး က binary သစ်ပင်တစ်ပင်သည် node တစ်ခုစီတွင် node တစ်ခုစီတွင်ရှိသော node များဖြင့်ဖွဲ့စည်းထားသောဘုံအချက်အလက်ဖွဲ့စည်းပုံမှာဖြစ်သည်။ များသောအားဖြင့်ဘယ်ဘက်ကလေး node ၏တန်ဖိုးသည်မှန်ကန်သောကလေး node ၏တန်ဖိုးထက်သေးငယ်သည်။ Binary Toroes သည်ကွန်ပျူတာသိပ္ပံတွင် Binary သစ်ပင်များ, မျှတသော binary သစ်ပင်များနှင့်အမှိုက်ပုံများကဲ့သို့သောကွန်ပျူတာသိပ္ပံတွင်ကျယ်ကျယ်ပြန့်ပြန့်အသုံးပြုကြသည်။ ဤဆောင်းပါးသည် PHP မှတစ်ဆင့် binary သစ်ပင်တစ်ပင်၏ဆင်ခြေလျှောကိုမည်သို့တွက်ချက်ရမည်ကိုရှင်းပြပါမည်။

Binary သစ်ပင်ဆင်ခြေလျှောကဘာလဲ

Binary Troke Slope သည်ဘယ်ဘက် subtree ၏ node ကိုတန်ဖိုးများနှင့် node တစ်ခုစီ၏ညာနိုတ်ပြတ်သားခြင်းနှင့်ဆက်စပ်မှု၏လုံးဝကွာခြားချက်ကိုရည်ညွှန်းသည်။ Binary သစ်ပင်၏ဆင်ခြေလျှောသည် node အားလုံး၏တောင်စောင်းများ၏ပေါင်းလဒ်ဖြစ်သည်။

PHP Code အကောင်အထည်ဖော်မှု

 
/**
 * Binary Tree Node Definition
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {
    public $res = 0;

    function findTilt($root) {
        $this->dfs($root);
        return $this->res;
    }

    // Binary သစ်ပင် slope တွက်ချက်ရန်အတိမ်အနက် - ပထမ ဦး ဆုံးရှာဖွေရေး
    function dfs($root) {
        if ($root == null) return 0;
        $left = $this->dfs($root->left);
        $right = $this->dfs($root->right);
        $this->res += abs($left - $right);
        return $left + $right + $root->val;
    }
}

အထက်ပါ PHP Code သည် Binary Tree Class ကိုအကောင်အထည်ဖော်ပြီး node တစ်ခုစီ၏ဆင်ခြေလျှောကိုတွက်ချက်ရန် DFS အနက်ပထမ ဦး ဆုံးရှာဖွေမှုမှတစ်ဆင့် node များကိုဖြတ်သန်းသွားသည်။ function ကို binary သစ်ပင်တစ်ခုလုံး၏တောင်စောင်းများ၏ပေါင်းလဒ်ကိုပြန်ပို့ရန် function ကိုအသုံးပြုသည်။ DFS function သည် node တစ်ခုစီကိုပြန်လည်ရယူပြီးလက်ဝဲ subtree ၏ပေါင်းလဒ်နှင့်လက်ရှိ node ၏ညာဘက် subtree ကိုပြန်ပို့သည်။

algorithm ခွဲခြမ်းစိတ်ဖြာ

binary tree slope ကိုတွက်ချက်ခြင်းလုပ်ငန်းစဉ်သည် node တစ်ခုစီ၏ဘယ်ဘက်နှင့်ညာအပိုင်းအစများအကြားခြားနားချက်၏အကြွင်းမဲ့တန်ဖိုးကိုတွက်ချက်ရန်လိုအပ်သည်။ traversal လုပ်ငန်းစဉ်အတွင်း node တစ်ခုစီ၏ဆင်ခြေလျှောတန်ဖိုးကိုစုဆောင်းထားပြီးဒှိပင်တစ်ခုလုံး၏ဆင်ခြေလျှောကိုနောက်ဆုံးတွင်ရရှိခဲ့သည်။

ဤတွက်ချက်မှုကိုအောင်မြင်ရန်ကျွန်ုပ်တို့သည်အောက်ခြေမှ binary သစ်ပင်ကိုဖြတ်သန်းရန် recursive နည်းလမ်းကိုအသုံးပြုသည်။ node တစ်ခုစီအတွက်၎င်း၏ဘယ်ဘက်၏တောင်စောင်းများကိုပထမ ဦး ဆုံးတွက်ချက်ထားပြီး၎င်းနှင့်လုံးဝခြားနားချက်၏အကြွင်းမဲ့တန်ဖိုးကိုထည့်သွင်းထားသည်။

အချိန်ရှုပ်ထွေးမှုသည်အို (n) ဖြစ်သည်။

အကျဉ်းချုပ်

ဤဆောင်းပါးသည် PHP မှတစ်ဆင့် Binary သစ်ပင်၏ဆင်ခြေလျှောကိုမည်သို့တွက်ချက်ရမည်ကိုဖော်ပြသည်။ နက်ရှိုင်းသောပထမရှာဖွေရေး algorithm ကို အသုံးပြု. Node တစ်ခုစီကိုပြန်လည်ရှာဖွေသည်။ algorithm တွင်အို (n) တွင်အချိန်ရှုပ်ထွေးမှုရှိသည်။ ၎င်းသည် Binary Troker Slope ပြ problem နာကိုကိုင်တွယ်ရန်ထိရောက်သောနည်းလမ်းဖြစ်သည်။