โปรแกรมค้นหาโหนดพิเศษในทรีใน Python

สมมติว่าเรามีรายการค่า 2 มิติที่เรียกว่า 'tree' ซึ่งแสดงถึง n-ary tree และรายการค่าอื่นที่เรียกว่า 'color' ต้นไม้จะแสดงเป็นรายการที่อยู่ติดกันและรากของมันคือต้นไม้[0].

ลักษณะของโหนดที่ i -

• tree[i] คือลูกและพ่อแม่ของมัน

• color[i] คือสีของมัน

เราเรียกโหนด N ว่า "พิเศษ" หากทุกโหนดในทรีย่อยที่มีรูทอยู่ที่ N มีสีเฉพาะ เรามีต้นไม้ต้นนี้ ต้องหาจำนวนโหนดพิเศษ

So, if the input is like tree = [
   [1,2],
   [0],
   [0,3],
   [2]
]

สี =[1, 2, 1, 1] แล้วผลลัพธ์จะเป็น 2

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ผลลัพธ์ :=0

• dfs(0, -1)

• ส่งคืนผลลัพธ์

• กำหนดฟังก์ชัน check_intersection() นี่จะใช้เวลาสี child_colors

  • ถ้า length of (colors)

    • สำหรับแต่ละ c ในสี ทำ

      • ถ้า c ใน child_colors ไม่ใช่ศูนย์ แล้ว

        • คืนค่า True

  • มิฉะนั้น

    • สำหรับแต่ละ c ใน child_colors ทำ

      • ถ้า c มีอยู่ใน child_colors แล้ว

        • คืนค่า True

• กำหนดฟังก์ชัน dfs() สิ่งนี้จะใช้โหนดก่อนหน้า

  • สี :={สี[โหนด]}

  • สำหรับเด็กแต่ละคนใน tree[node] ทำ

    • ถ้าลูกไม่เหมือนเดิมแล้ว

      • child_colors :=dfs(ลูก, โหนด)

      • หากสีและ child_colors ไม่ว่างเปล่า

        • ถ้า check_intersection(colors, child_colors) ไม่ใช่ศูนย์ แล้ว

          • สี :=null

        • มิฉะนั้น

          • ถ้าความยาวของ (สี) <ความยาวของ (child_colors) แล้ว

            • child_colors :=child_colors หรือสี

            • สี :=child_colors

          • มิฉะนั้น

            • สี :=สี OR child_colors

      • มิฉะนั้น

        • สี :=null

    • ถ้าสีไม่หมดก็

      • ผลลัพธ์ :=ผลลัพธ์ + 1

    • คืนค่าสี

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

import collections
class Solution:
   def solve(self, tree, color):
      self.result = 0
      def dfs(node, prev):
         colors = {color[node]}
         for child in tree[node]:
            if child != prev:
               child_colors = dfs(child, node)
               if colors and child_colors:
                  if self.check_intersection(colors, child_colors):
                     colors = None
                  else:
                     if len(colors) < len(child_colors):
                        child_colors |= colors
                        colors = child_colors
                     else:
                        colors |= child_colors
                  else:
                     colors = None
            if colors:
               self.result += 1
            return colors
         dfs(0, -1)
         return self.result
      def check_intersection(self, colors, child_colors):
         if len(colors) < len(child_colors):
            for c in colors:
               if c in child_colors:
                  return True
         else:
            for c in child_colors:
               if c in colors:
                  return True
ob = Solution()
print(ob.solve( [
   [1,2],
   [0],
   [0,3],
   [2]
], [1, 2, 1, 1]))

อินพุต

[
   [1,2],
   [0],
   [0,3],
   [2]
], [1, 2, 1, 1]

ผลลัพธ์

2