สมมติว่าเรามีไบนารีทรีที่มีค่า 0, 1 และ 2 รูทมีอย่างน้อย 0 โหนดและ 1 โหนด ตอนนี้ สมมติว่ามีการดำเนินการที่เราลบขอบในต้นไม้ และต้นไม้กลายเป็นต้นไม้สองต้นที่แตกต่างกัน เราต้องหาจำนวนวิธีที่เราสามารถลบขอบด้านหนึ่งได้ โดยที่ต้นไม้ทั้งสองต้นไม่ได้มีทั้งโหนด 0 และโหนด 1 โหนด
ดังนั้นหากอินพุตเป็นแบบ
จากนั้นผลลัพธ์จะเป็น 1 เนื่องจากเราสามารถลบขอบ 0 ถึง 2 เท่านั้น
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- นับ :=[0, 0, 0]
- กำหนดฟังก์ชัน dfs() นี่จะใช้โหนด
- ถ้าโหนดไม่เป็นโมฆะ
- ก่อน :=นับ
- dfs(ด้านซ้ายของโหนด)
- dfs(ด้านขวาของโหนด)
- count[value of node] :=count[value of node] + 1
- node.count :=รายการของ (count[i] - pre[i]) สำหรับ i คือ 0 และ 1
- กำหนดฟังก์ชัน dfs2() นี่จะเป็นโหนดพาร์
- ถ้าโหนดไม่เป็นโมฆะ
- ถ้าพาร์ไม่เป็นค่าว่าง
- (a0, a1) :=จำนวนโหนด
- (b0, b1) :=(นับ[0] - a0, นับ[1] - a1)
- ถ้า (a0 เหมือนกับ 0 หรือ a1 เหมือนกับ 0) และ (b0 เหมือนกับ 0 หรือ b1 เหมือนกับ 0) แล้ว
- อัน :=ans + 1
- dfs2(ด้านซ้ายของโหนด โหนด)
- dfs2(ด้านขวาของโหนด โหนด)
- ถ้าพาร์ไม่เป็นค่าว่าง
- จากวิธีหลัก ให้ทำดังต่อไปนี้ −
- dfs(root)
- ตอบ :=0
- dfs2(root)
- คืนสินค้า
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class TreeNode: def __init__(self, data, left = None, right = None): self.val = data self.left = left self.right = right class Solution: def solve(self, root): count = [0, 0, 0] def dfs(node): if node: pre = count[:] dfs(node.left) dfs(node.right) count[node.val] += 1 node.count = [count[i] - pre[i] for i in range(2)] dfs(root) def dfs2(node, par=None): if node: if par is not None: a0, a1 = node.count b0, b1 = count[0] - a0, count[1] - a1 if (a0 == 0 or a1 == 0) and (b0 == 0 or b1 == 0): self.ans += 1 dfs2(node.left, node) dfs2(node.right, node) self.ans = 0 dfs2(root) return self.ans ob = Solution() root = TreeNode(0) root.left = TreeNode(0) root.right = TreeNode(2) root.right.left = TreeNode(1) root.right.right = TreeNode(1) print(ob.solve(root))
อินพุต
root = TreeNode(0) root.left = TreeNode(0) root.right = TreeNode(2) root.right.left = TreeNode(1) root.right.right = TreeNode(1)
ผลลัพธ์
1
