ປົ່ງຮາກອອກຕາມເສັ້ນທາງຂອງໃບໄມ້ໂດຍລວມເປົ້າ ໝາຍ Leetcode Solutions


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon ຈາກຫນາກແອບເປີ ເຟສບຸກ Microsoft
ການຄົ້ນຫາຄວາມເລິກຄັ້ງ ທຳ ອິດ ຕົ້ນໄມ້

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

ປົ່ງຮາກອອກຕາມເສັ້ນທາງຂອງໃບໄມ້ໂດຍລວມເປົ້າ ໝາຍ Leetcode Solutions

    2
    
  /    \
  
1        4
 
       /     \

     1         4

K = 7
Path Present
     2
          
  /     \

1         4

       /     \

     1          3

K = 6
No such path

 

ວິທີການ

ວິທີການແມ່ນງ່າຍດາຍຫຼາຍ. ພວກເຮົາສາມາດກວດເບິ່ງໄດ້ວ່າຖ້າໃນຈຸດໃດ ໜຶ່ງ, ຄ່າຂອງ node ແມ່ນສິ່ງທີ່ພວກເຮົາຕ້ອງການ, ແລະມັນກໍ່ແມ່ນໃບໄມ້ເຊັ່ນກັນ. ຈາກນັ້ນ, ພວກເຮົາສາມາດສະຫຼຸບໄດ້ວ່າເສັ້ນທາງມີມາແຕ່ຮາກເຖິງຈຸດນີ້ມີຍອດລວມເປົ້າ ໝາຍ. ສະນັ້ນ, ມັນເປັນຄວາມຕັ້ງໃຈທີ່ພວກເຮົາເຕັ້ນໄປຫາເດັກນ້ອຍຄົນໃດຄົນ ໜຶ່ງ, ພວກເຮົາຕ້ອງໄດ້ຜ່ານຍອດທີ່ຍັງເຫຼືອເພື່ອເຮັດໃຫ້ ສຳ ເລັດຕາມເປົ້າ ໝາຍ.

ແນວຄວາມຄິດນີ້ເຮັດວຽກຢູ່ໃນ ໜັງ ສືຜ່ານແດນດຽວ ເປັນໄມ້ຢືນຕົ້ນ.

ລະບົບວິເຄາະ

  1. ສ້າງ ໜ້າ ທີ່ຊ່ວຍຜູ້ປະຕິເສດ
  2. ຟັງຊັນ Helper ມີລາຍລະອຽດຂອງ node ປັດຈຸບັນແລະຜົນລວມທີ່ຍັງເຫຼືອ
  3. ຖ້າຮາກປະຈຸບັນແມ່ນ NULL,
    • ການກັບຄືນມາ false, ເປັນຂໍ້ນີ້ບໍ່ສາມາດປະກອບສ່ວນຫຍັງໄດ້.
  4. ຖ້າຮາກປະຈຸບັນແມ່ນ ບໍ່ NULL
    • ຖ້າຜົນລວມທີ່ຕ້ອງການເທົ່າກັບຄ່າ node ແລະ node ແມ່ນໃບໄມ້
      • ກັບຄືນມາເປັນຄວາມຈິງ
    • ອື່ນ
      • ກວດເບິ່ງວ່າມີ ຄຳ ບັນຍັດຊ້າຍຫລືເດັກໃດທີ່ຕອບສະ ໜອງ ຄວາມຕ້ອງການກັບຜົນລວມທີ່ຕ້ອງການ: current_sum - node_value
  5. ພິມຜົນຜະລິດ

ການປະຕິບັດ

ໂປຣແກຣມ C ++ ເພື່ອຊອກຫາເສັ້ນທາງຂອງ Root ກັບ Leaf ດ້ວຍຜົນລວມຂອງເປົ້າ ໝາຍ

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

bool pathSumEqualToTarget(treeNode* root , int target)
{
    if(!root)
        return false;
    if(target == root->value && !root->left && !root->right)
        return true;
    return pathSumEqualToTarget(root->left , target - root->value) || pathSumEqualToTarget(root->right , target - root->value);
}


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

    int K = 7;

    if(pathSumEqualToTarget(root , K))
        cout << "Path Present" << '\n';
    else
        cout << "No such path" << '\n';

}

 

Java Program ເພື່ອຊອກຫາເສັ້ນທາງຂອງ Root ກັບ Leaf ໂດຍມີເປົ້າ ໝາຍ ລວມ

class treeNode
{
    int value;
    treeNode left , right;

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

class path_sum
{
    public static boolean pathSumEqualToTarget(treeNode root , int target)
    {
        if(root == null)
            return false;
        if(root.value == target && root.left == null && root.right == null)
            return true;
        return pathSumEqualToTarget(root.left , target - root.value) || pathSumEqualToTarget(root.right , target - root.value);
    }


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

        int K = 7;

        if(pathSumEqualToTarget(root , K))
            System.out.println("Path Present");
        else
            System.out.println("No such path");
    }
}

ການວິເຄາະຄວາມສັບສົນ

ຄວາມຊັບຊ້ອນເວລາໃນການຊອກຫາເສັ້ນທາງ Root ຫາເສັ້ນທາງທີ່ມີຜົນລວມ

ໂອ (N), ຍ້ອນວ່າໂປຣແກຣມເຮັດວຽກຢູ່ໃນໃບໄມ້ສອງໃບໃນກໍລະນີຮ້າຍແຮງທີ່ສຸດ.

ຄວາມສັບສົນໃນອະວະກາດເພື່ອຊອກຫາເສັ້ນທາງຂອງ Root ກັບ Leaf ດ້ວຍຜົນລວມ

ໂອ (N). Recursion ໃຊ້ຊ່ອງ stack ຊ່ວຍ.