ຜົນລວມຂອງວິທີແກ້ໄຂໃບລານເບື້ອງຊ້າຍ  


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Adobe
ຂັ້ນຕອນວິທີ ລະຫັດ ການສໍາພາດ ການສໍາພາດກ່ອນ LeetCode LeetCodeSolutions ຕົ້ນໄມ້ Traversal ຕົ້ນໄມ້

ໃນບັນຫານີ້, ພວກເຮົາຕ້ອງຊອກຫາຜົນລວມຂອງໃບປະໄວ້ທັງ ໝົດ ໃນຖານສອງ ເປັນໄມ້ຢືນຕົ້ນ. ໃບໄມ້ໃບປະໄວ້” ຖ້າວ່າມັນແມ່ນເດັກນ້ອຍທີ່ຍັງເຫລືອຢູ່ຂອງຕົ້ນໄມ້ຢູ່ໃນຕົ້ນໄມ້.

ຜົນລວມຂອງວິທີແກ້ໄຂໃບລານເບື້ອງຊ້າຍPin

ຍົກຕົວຢ່າງ    

     2
        
  /     \

4          7

        /      \

      9          4
Sum is 13
2

  \
 
    3
Sum is 0

ວິທີການ  

ພວກເຮົາສາມາດໃຊ້ການເອີ້ນຄືນເພື່ອຂ້າມຕົ້ນໄມ້ຖານສອງ. ຖ້າຂໍ້ໃດ ໜື່ງ ມີເດັກຢູ່ເບື້ອງຊ້າຍແລະມັນກໍ່ແມ່ນໃບໄມ້ເຊັ່ນດຽວກັນ, ພວກເຮົາສາມາດເພີ່ມມູນຄ່າຂອງເດັກເບື້ອງຊ້າຍເຂົ້າໃນຍອດຂອງພວກເຮົາ. ແຕ່ວິທີການນີ້ໃຊ້ພື້ນທີ່ເຮັດວຽກທີ່ເອີ້ນຄືນ.

ພວກເຮົາສາມາດ ນຳ ໃຊ້ສິ່ງອື່ນໆທີ່ສາມາດປະຫຍັດພື້ນທີ່ຄວາມ ຈຳ ໄດ້ບໍ?

Morris Inorder Traversal ສາມາດຈັດຕັ້ງປະຕິບັດເພື່ອໄປຢ້ຽມຢາມທຸກໆໂຫນດ. ກວດເບິ່ງວ່າມັນມີລູກໃບເບື້ອງຊ້າຍແລະເພີ່ມມູນຄ່າຂອງມັນໃຫ້ ເໝາະ ສົມກັບຜົນໄດ້ຮັບບໍ່. ນີ້ແມ່ນວິທີການທີ່ດີທີ່ສຸດ. ໃຫ້ສັງເກດວ່າພວກເຮົາສາມາດຈັດຕັ້ງປະຕິບັດ“ ການເດີນທາງຂອງ Morris Inorder” ພຽງແຕ່ຖ້າວ່າບັນຫານັ້ນຊ່ວຍໃຫ້ພວກເຮົາປ່ຽນໂຄງສ້າງຂອງຕົ້ນໄມ້.

ສູດການຄິດໄລ່ (ຄິດໄລ່)  

  1. ສ້າງ ໜ້າ ທີ່ sumOfLeftLeaves () ທີ່ສົ່ງຜົນຕອບແທນຂອງໃບເບື້ອງຊ້າຍຂອງໃບຜ່ານໄປ ຮາກ
  2. ຖ້າຮາກຂອງຕົ້ນໄມ້ແມ່ນ NULL
    • ກັບຄືນສູນ
  3. ຖ້າຫາກວ່າຮາກໃນປະຈຸບັນມີລູກທີ່ເຫລືອຢູ່ແລະມັນແມ່ນກ ໃບ
    • ສົ່ງມູນຄ່າຂອງມັນ + sumOfLeftLEaves (ຮາກ -> ຊ້າຍ) + sumOfLeftLeaves (ຮາກ -> ຂວາ)
  4. ກັບຄືນ sumOfLeftLEaves (ຮາກ -> ຊ້າຍ) + sumOfLeftLeaves (ຮາກ -> ຂວາ)
ເບິ່ງ
ຊອກຫາຜູ້ຊະນະໃນເຄື່ອງຫຼີ້ນ Tic Tac Toe ເກມ Leetcode Solution

ສູດການຄິດໄລ່ (Morris Inorder)  

  1. Traverse ໄບນາລີໂດຍໃຊ້ Morris Inorder Traversal:
    • ກະທູ້ບອກກ່ອນລ່ວງ ໜ້າ ຂອງລັດຖະບັນຍັດເບື້ອງຊ້າຍຂອງຂໍ້ຕໍ່ກັບຕົວມັນເອງ.
    • ຖ້າກະທູ້ມີຢູ່ແລ້ວ, ບໍ່ຄວນອ່ານເພື່ອຮັກສາໂຄງສ້າງຕົ້ນໄມ້ຂອງຕົ້ນໄມ້.
  2. ຖ້າເດັກເບື້ອງຊ້າຍຂອງຂໍ້ໃດກໍ່ຕາມແມ່ນໃບໄມ້, ໃຫ້ຕື່ມມັນໃສ່ຜົນ.
  3. ພິມຜົນໄດ້ຮັບ.

ການປະຕິບັດ  

C ++ ໂປຣແກຣມຂອງ Sum of Solutions Leetcode Solutions

ວິທີການແບບທົດແທນ

#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

Java Program of Sum of Solutions ໃບເບື້ອງຊ້າຍ

ວິທີການແບບທົດແທນ

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  

ຄວາມສັບສົນເວລາ

ໂອ (N), ດັ່ງທີ່ພວກເຮົາຂ້າມຕົ້ນໄມ້ທັງ ໝົດ ເທື່ອ ໜຶ່ງ ໃນທັງແບບທີ່ລວບລວມແລະວິທີການປ່ຽນແປງ.

ເບິ່ງ
ເວລາທີ່ດີທີ່ສຸດທີ່ຈະຊື້ແລະຂາຍຫຸ້ນ

ຄວາມສັບສົນໃນອະວະກາດ

O (1) ການ ນຳ ໃຊ້ Morris Inorder Traversal. ວິທີການທີ່ຈະເອີ້ນຄືນຈະໃຊ້ ໂອ (N) ຊ່ອງໃນຄວາມຊົງ ຈຳ.