مجموع برگهای چپ راه حلهای کد  


سطح دشواری ساده
اغلب در خشت
الگوریتم برنامه نویسی مصاحبه مصاحبه آماده LeetCode LeetCodeSolutions درخت عبور از درخت

در این مشکل ، ما باید مجموع برگهای باقی مانده را در یک باینری پیدا کنیم درخت. برگی که به آن "برگ چپاگر کودک چپ گره از درخت باشد.

مجموع برگهای چپ راه حلهای کدسنجاق

مثال    

     2
        
  /     \

4          7

        /      \

      9          4
Sum is 13
2

  \
 
    3
Sum is 0

روش  

برای عبور از درخت باینری می توانیم از بازگشت استفاده کنیم. اگر هر گره ای فرزند چپ داشته باشد و یک برگ نیز باشد ، می توانیم مقدار فرزند چپ را به جمع خود اضافه کنیم. اما این روش از فضای پشته بازگشتی استفاده می کند.

آیا می توان از تراورس دیگری استفاده کرد که بتواند فضای حافظه را ذخیره کند؟

پیمایش Morris Inorder می تواند برای بازدید از هر گره بصورت تکراری اجرا شود. بررسی کنید که آیا آن دارای یک برگ برگ چپ است یا خیر و بر این اساس مقدار آن را در نتیجه اضافه کنید. این رویکرد بهینه است. توجه داشته باشید که فقط درصورتی که مشکل به ما اجازه تغییر ساختار درخت را بدهد ، می توانیم "پیمایش Morris Inorder" را اجرا کنیم.

الگوریتم (بازگشتی)  

  1. ایجاد یک تابع sumOfLeftLeaves () که جمع برگهای چپ هر برگرده را برمی گرداند ریشه
  2. اگر ریشه درخت باشد NULL
    • برگشت صفر
  3. اگر ریشه فعلی دارای یک فرزند چپ است و آن یک است برگ
    • مقدار + sumOfLeftLEaves خود را برگردانید (root-> چپ) + sumOfLeftLeaves (root-> right)
  4. sumOfLeftLEaves را برگردانید (root-> چپ) + sumOfLeftLeaves (root-> right)
همچنین مشاهده کنید
برنده بازی Tic Tac Toe بازی Leetcode Solution باشید

الگوریتم (Morris Inorder)  

  1. با استفاده از Morris Inorder Traversal باینری را رد کنید:
    • ناسازگار سلف زیر شاخه سمت چپ از هر گره را به خودش.
    • اگر یک نخ قبلاً وجود دارد ، آن را از نخ خارج کنید تا ساختار اصلی درخت حفظ شود.
  2. اگر کودک سمت چپ هر گره ای یک برگ است ، آن را به نتیجه اضافه کنید.
  3. نتیجه را چاپ کنید.

پیاده سازی  

برنامه ++ C از مجموع محلولهای Leetcode برگهای چپ

رویکرد بازگشتی

#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

برنامه جاوا از مجموعه راه حل های Leetcode Left Leaves

رویکرد بازگشتی

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

تجزیه و تحلیل پیچیدگی حاصل از محلول های Leetcode برگ های چپ  

پیچیدگی زمان

بر)، همانطور که ما کل درخت را یک بار در دو رویکرد بازگشتی و تکراری رد می کنیم.

همچنین مشاهده کنید
بهترین زمان برای خرید و فروش سهام

پیچیدگی فضا

O (1) با استفاده از Morris Inorder Traversal. رویکرد بازگشتی انجام می شود بر) فضای حافظه.