Độ sâu tối đa 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ìm độ sâu tối đa của cái cây đó. Độ sâu tối đa của cây là số lượng nút tối đa được vượt qua để đến được chiếc lá từ gốc bằng con đường dài nhất. Giả sử cái cây như dưới đây. Độ sâu sẽ là 3 ở đây.

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

• Ở đây chúng tôi sẽ sử dụng phương pháp đệ quy. Phương pháp là giải quyết (root, depth =0)
• nếu gốc trống, sau đó trả về độ sâu
• nếu không, trả về tối đa của giải (trái, độ sâu + 1) và giải quyết (bên trái, độ sâu + 1)

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

Ví dụ

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):
         if data is not None:
            temp.left = TreeNode(data)
         else:
            temp.left = TreeNode(0)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
         if data is not None:
            temp.right = TreeNode(data)
         else:
            temp.right = TreeNode(0)
         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 maxDepth(self, root):
      """
      :type root: TreeNode
      :rtype: int
      """
      return self.solve(root)
   def solve(self,root,depth = 0):
      if root == None:
         return depth
      return max(self.solve(root.left,depth+1),self.solve(root.right,depth+1))
tree1 = make_tree([1,2,2,3,4,None,3])
ob1 = Solution()
print(ob1.maxDepth(tree1))

Đầu vào

tree1 = make_tree([1,2,2,3,4,None,3])

Đầu ra

3