home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

ตรวจสอบว่า Leaf Traversal ของ Binary Tree สองต้น เหมือนกันหรือไม่ด้วย Python

สมมติมี Binary Tree สองต้น ต้องตรวจสอบว่า Leaf Traversal (ลำดับ Leaf จากซ้ายไปขวา) เหมือนกันหรือไม่

เช่น Tree 1 และ Tree 2 มี Leaf Sequence [5, 7, 8] -> Output True

ตรวจสอบว่า Leaf Traversal ของ Binary Tree สองต้น เหมือนกันหรือไม่ด้วย Python

ขั้นตอนแก้ (Iterative DFS with Stack):

  • ใช้ Stack s1, s2 สำหรับ Root1, Root2
  • Pop Node ถ้าไม่ใช่ Leaf Push Right แล้ว Left (เพื่อให้ Left ถูก Process ก่อน)
  • เมื่อเจอ Leaf ทั้งคู่ เปรียบเทียบค่า ถ้าไม่เท่ากัน Return False
  • ถ้าหนึ่ง Tree จบก่อนอีกต้น Return False

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

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = self.right = None
    def is_leaf(self):
        return self.left == None and self.right == None

def solve(r1, r2):
    s1 = []
    s2 = []
    s1.append(r1)
    s2.append(r2)
    while len(s1) != 0 or len(s2) != 0:
        if len(s1) == 0 or len(s2) == 0:
            return False
        r1_node = s1.pop(-1)
        while r1_node != None and not r1_node.is_leaf():
            if r1_node.right != None:
                s1.append(r1_node.right)
            if r1_node.left != None:
                s1.append(r1_node.left)
                r1_node = s1.pop(-1)
        r2_node = s2.pop(-1)
        while r2_node != None and not r2_node.is_leaf():
            if r2_node.right != None:
                s2.append(r2_node.right)
            if r2_node.left != None:
                s2.append(r2_node.left)
            r2_node = s2.pop(-1)
        if r1_node == None and r2_node != None:
            return False
        if r1_node != None and r2_node == None:
            return False
        if r1_node != None and r2_node != None:
            if r1_node.val != r2_node.val:
                return False
    return True

root1 = TreeNode(2)
root1.left = TreeNode(3)
root1.right = TreeNode(4)
root1.left.left = TreeNode(5)
root1.right.left = TreeNode(7)
root1.right.right = TreeNode(8)
root2 = TreeNode(1)
root2.left = TreeNode(6)
root2.right = TreeNode(9)
root2.left.right = TreeNode(5)
root2.right.left = TreeNode(7)
root2.right.right = TreeNode(8)
print(solve(root1, root2))

Input

root1 = TreeNode(2) root1.left = TreeNode(3) root1.right = TreeNode(4) root1.left.left = TreeNode(5) root1.right.left = TreeNode(7) root1.right.right = TreeNode(8) root2 = TreeNode(1) root2.left = TreeNode(6) root2.right = TreeNode(9) root2.left.right = TreeNode(5) root2.right.left = TreeNode(7) root2.right.right = TreeNode(8)

Output

True