Left Leaves Leumcode Solutions ပေါင်းလဒ်


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Adobe က
သစ်ပင် သစ်ပင်လှည့်လည်

ဒီပြproblemနာမှာဘယ်ဘက်ရွက်အားလုံးရဲ့ပေါင်းလဒ်ကို binary မှာရှာရမယ် သစ်ပင်။ "ဟုခေါ်တွင်သောအရွက်Left Leafဒါကြောင့်သစ်ပင်၌မဆို node ကိုတစ် ဦး လက်ဝဲကလေးကဖြစ်လျှင် "။

Left Leaves Leumcode Solutions ပေါင်းလဒ်

နမူနာ  

     2
        
  /     \

4          7

        /      \

      9          4
Sum is 13
2

  \
 
    3
Sum is 0

ချဉ်းကပ်နည်း

ကျနော်တို့က binary သစ်ပင်ဖြတ်သန်းရန် recursion ကိုသုံးနိုင်သည်။ မည်သည့်ဆုံမှတ်တွင်ကျန်ရှိသောကလေးရှိပါသလဲ၎င်းသည်အရွက်လည်းဖြစ်ပါကဘယ်ဘက်ကလေး၏တန်ဖိုးကိုကျွန်ုပ်တို့၏ပေါင်းလဒ်ထဲထည့်နိုင်သည်။ သို့သော်ဤချဉ်းကပ်မှုသည် recursive stack space ကိုအသုံးပြုသည်။

မှတ်ဉာဏ်နေရာကိုသိမ်းဆည်းနိုင်သောအခြားဖြတ်သန်းခြင်းကိုကျွန်ုပ်တို့အသုံးပြုနိုင်ပါသလား။

မောရစ် Inorder ဖြတ်သန်း node များအားတိုင်းလည်ပတ်ရန်အတွက်အကောင်အထည်ဖော်နိုင်သည်။ သူ၌လက်ဝဲရွက်ကလေးရှိမရှိစစ်ဆေးပြီးရလဒ်အနေဖြင့်၎င်း၏တန်ဖိုးကိုထည့်ပါ။ ဤသည်အကောင်းဆုံးချဉ်းကပ်မှုဖြစ်ပါတယ်။ သတိပြုရန်မှာပြMorနာကသစ်ပင်၏ဖွဲ့စည်းပုံကိုပြောင်းလဲရန်ခွင့်ပြုမှသာလျှင်“ Morris Inorder traversal” ကိုကျွန်ုပ်တို့အကောင်အထည်ဖော်နိုင်သည်။

Algorithm (Recursive)

  1. function တစ်ခုဖန်တီးပါ sumOfLeftLeaves () ကြောင်းလွန်မဆို၏ဘယ်ဘက်အရွက်၏ပေါင်းလဒ်ပြန်လာသည် အမြစ်
  2. သစ်ပင်၏အမြစ်သည်ဆိုပါက null
    • သုညသို့ပြန်သွားသည်
  3. အကယ်၍ လက်ရှိအမြစ်သည်လက်ဝဲကလေးတစ် ဦး ရှိပြီး၎င်းသည် အရွက်
    • ၎င်း၏တန်ဖိုးကို + sumOfLeftLEaves (root-> left) + sumOfLeftLeaves (root-> right) သို့ပြန်သွားပါ
  4. sumOfLeftLEaves (root-> left) + sumOfLeftLeaves (root-> right) သို့ပြန်သွားပါ။

Algorithm (မောရစ် Inorder)

  1. Morris Inorder Traversal ကို အသုံးပြု၍ binary ကိုဖြတ်သန်းပါ။
    • မည်သည့် node ကိုမဆိုဘယ်ဘက် subtree ၏ inorder predecessor ကိုသူ့ထံပို့ပေးပါ။
    • ချည်တစ်ခုရှိပြီးသားဖြစ်ပါကသစ်ပင်၏မူလတည်ဆောက်ပုံကိုဆက်လက်ထိန်းသိမ်းထားရန်၎င်းကိုဖြုတ်ပစ်ပါ။
  2. မည်သည့် node တစ်ခု၏ဘယ်ဘက်ကလေးသည်အရွက်ဖြစ်လျှင်၎င်းကိုရလဒ်သို့ထည့်ပါ။
  3. ရလဒ်ပုံနှိပ်ပါ။

အကောင်အထည်ဖော်ရေး

Left Leaves Leetcode Solutions ၏စုစုပေါင်း၏ C ++ အစီအစဉ်

Recursive ချဉ်းကပ်နည်း

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

int sumOfLeftLeaves(treeNode* root)
{
    if(root)
    {
        if(root->left && !root->left->left && !root->left->right)
            return root->left->value + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
        return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
    }
    return 0;
}

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

    cout << "Sum is " << sumOfLeftLeaves(root) << "\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 sumOfLeftLeaves(treeNode* root)
{
    int sum = 0;
    while(root != NULL)
    {
        if(root->left == NULL)
        {
            if(root->left != NULL && root->left->left == NULL && root->left->right == NULL)
                sum += root->left->value;
            root = root->right;
        }
        else
        {
            treeNode* temp = root->left;
            while(temp->right != NULL && temp->right != root)
                temp = temp->right;

            if(temp->right == NULL)
            {
                temp->right = root;
                root = root->left;
            }
            else
            {
                temp->right = NULL;
                if(root->left != NULL && root->left->left == NULL && root->left->right == NULL)
                    sum += root->left->value;
                root = root->right;
            }
        }
    }
    return sum;
}



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

    cout << "Sum is " << sumOfLeftLeaves(root) << "\n";


    return 0;
}
Sum is 13

Left Leaves of Sumet of Leetcode Solutions ၏ဂျာဗားအစီအစဉ်

Recursive ချဉ်းကပ်နည်း

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

class sum_of_left_leaves
{
    public static int sumOfLeftLeaves(treeNode root)
    {
        if(root == null)
            return 0;
        if(root.left != null && root.left.left == null && root.left.right == null)
            return root.left.value + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
        return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
    }


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

        System.out.println("Sum is " + sumOfLeftLeaves(root));
    }
}

အကောင်းဆုံးနည်းလမ်း

int sum = 0;
        while(root != null)
        {
            if(root.left == null)
            {
                if(root.left != null && root.left.left == null && root.left.right == null)
                    sum += root.left.value;
                root = root.right;
            }
            else
            {
                treeNode temp = root.left;
                while(temp.right != null && temp.right != root)
                    temp = temp.right;

                if(temp.right == null)
                {
                    temp.right = root;
                    root = root.left;
                }
                else
                {
                    temp.right = null;
                    if(root.left != null && root.left.left == null && root.left.right == null)
                        sum += root.left.value;
                    root = root.right;
                }
            }
        }
        return sum;
Sum is 13

Left Le Leccode Solutions ၏ရှုပ်ထွေးမှုအားသုံးသပ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N)၊ ကျနော်တို့တစ်ချိန်က recursive နှင့်ကြားမှာချဉ်းကပ်မှုအတွက်တစ်ချိန်ကသစ်ပင်ဖြတ်သန်းအဖြစ်။

အာကာသရှုပ်ထွေးမှု

အို (၁) မောရစ် Inorder ဖြတ်သန်းသုံးနိုင်သည်။ တုံ့ပြန်မှုချဉ်းကပ်မှုယူလိမ့်မယ် အို (N) မှတ်ဉာဏ်ထဲမှာအာကာသ.