เส้นผ่านศูนย์กลางของต้นไม้แบบทวิภาคใน Python

สมมติว่าเรามีต้นไม้แบบทวิภาค เราต้องคำนวณความยาวของเส้นผ่านศูนย์กลางของต้นไม้ เส้นผ่านศูนย์กลางของต้นไม้แบบทวิภาคคือความยาวของเส้นทางที่ยาวที่สุดระหว่างโหนด任意สองโหนดในต้นไม้ เส้นทางนี้ไม่จำเป็นต้องผ่านราก (root) เช่น ถ้าต้นไม้เป็นแบบด้านล่าง เส้นผ่านศูนย์กลางจะเป็น 3 เนื่องจากความยาวของเส้นทาง [4,2,1,3] หรือ [5,2,1,3] คือ 3

วิธีการแก้ปัญหา

• เราจะใช้ DFS เพื่อหาเส้นผ่านศูนย์กลาง ตั้งค่า answer := 0
• เรียกฟังก์ชัน dfs กับราก dfs(root)
• dfs จะทำงานดังนี้ dfs(node):
  • ถ้าโหนดไม่มีอยู่ ให้คืนค่า 0
  • left := dfs(โหนดซ้ายของราก), และ right := dfs(โหนดขวาของราก)
  • answer := ค่าสูงสุดระหว่าง answer และ left + right
  • คืนค่าค่าสูงสุดระหว่าง left + 1 และ right + 1

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

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

def insert(temp, data):
    que = []
    que.append(temp)
    while len(que):
        temp = que[0]
        que.pop(0)
        if not temp.left:
            temp.left = TreeNode(data)
            break
        else:
            que.append(temp.left)
        if not temp.right:
            temp.right = TreeNode(data)
            break
        else:
            que.append(temp.right)

def make_tree(elements):
    Tree = TreeNode(elements[0])
    for element in elements[1:]:
        insert(Tree, element)
    return Tree

class Solution(object):
    def diameterOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.ans = 0
        self.dfs(root)
        return self.ans

    def dfs(self, node):
        if not node:
            return 0
        left = self.dfs(node.left)
        right = self.dfs(node.right)
        self.ans = max(self.ans, right + left)
        return max(left + 1, right + 1)

root = make_tree([1,2,3,4,5])
ob1 = Solution()
print(ob1.diameterOfBinaryTree(root))

อินพุต

[1,2,3,4,5]

เอาต์พุต

3