Đường kính của cây nhị phân trong Python

Giả sử chúng ta có một cây nhị phân; chúng ta phải tính chiều dài đường kính của cây. Đường kính của cây nhị phân thực sự là độ dài của đường đi dài nhất giữa hai nút bất kỳ trong cây. Đường dẫn này không nhất thiết phải đi qua gốc. Vì vậy, nếu cái cây giống như bên dưới, thì đường kính sẽ là 3 trong khi chiều dài của đường dẫn [4,2,1,3] hoặc [5,2,1,3] là 3

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Chúng tôi sẽ sử dụng dfs để tìm đường kính, đặt câu trả lời:=0
• gọi hàm dfs với dfs gốc (root)
• dfs sẽ hoạt động giống như bên dưới dfs (nút)
• nếu nút không có, thì trả về 0
• left:=dfs (cây con bên trái của gốc) và right:=dfs (cây con bên phải của gốc)
• answer:=max of answer và left + right
• trả về giá trị tối đa bên trái + 1 và bên phải + 1

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

[1,2,3,4,5]

Đầu ra

3