ลบโหนดที่มีลูกเพียงข้างเดียวออกจาก Binary Tree ใน Python

กำหนด Binary Tree root ลบโหนดที่มีลูกเพียงข้างเดียว (left XOR right) ออก ให้ลูกขึ้นแทนที่

ตัวอย่าง: →

แนวทาง (Recursive)

1. Base case: root เป็น None หรือ leaf → คืน root
2. ถ้ามีลูกข้างเดียว → คืนผลลัพธ์ของการ solve ลูกข้างนั้นแทน
3. ถ้ามีครบทั้งสองข้าง → solve ทั้งสองข้าง แล้วคืน root

ตัวอย่างโค้ด

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

def print_tree(root):
    if root is not None:
        print_tree(root.left)
        print(root.data, end=', ')
        print_tree(root.right)

class Solution:
    def solve(self, root):
        if not root:
            return root
        if not root.left and not root.right:
            return root
        if not root.left:
            return self.solve(root.right)
        if not root.right:
            return self.solve(root.left)
        root.left = self.solve(root.left)
        root.right = self.solve(root.right)
        return root

ob = Solution()
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.right.right = TreeNode(5)
root.left.left.right = TreeNode(6)
root.right.right.left = TreeNode(7)
root.right.right.right = TreeNode(8)

res = ob.solve(root)
print_tree(res)  # 6, 1, 7, 5, 8,

อินพุต

TreeNode structure as above

เอาต์พุต

6, 1, 7, 5, 8,