在 Python 中查找具有相同左子树和右子树的最大子树

pythonserver side programmingprogramming更新于 2025/10/10 13:00:17

假设我们有一棵二叉树;我们必须找到具有相同左子树和右子树的最大子树。首选时间复杂度为 O(n)。

因此,如果输入如下

然后输出将是

为了解决这个问题,我们将遵循以下步骤 −

  • 定义一个函数solve()。这将获取 root、encode、maxSize、maxNode

  • 如果 root 为 None,则

    • 返回 0

  • left_list := 带有空白字符串的列表

  • right_list := 带有空白字符串的列表

  • ls := resolve(root.left, left_list, maxSize, maxNode)

  • rs := resolve(root.right, right_list, maxSize, maxNode)

  • size := ls + rs + 1

  • 如果 left_list[0] 与 right_list[0] 相同,则

    • 如果 size > maxSize[0],然后

      • maxSize[0] := size

      • maxNode[0] := root

  • encode[0] := encode[0] 连接 "|" 连接 left_list[0] 连接 "|"

  • encode[0] := encode[0] 连接 "|" 连接 str(root.data) 连接 "|"

  • encode[0] := encode[0] 连接 "|"连接 right_list[0] 连接 "|"

  • 返回大小

  • 从主方法中,执行以下操作 −

  • maximum := [0]

  • encode := 带有空白字符串的列表

  • solve(node, encode, maximum, maxNode)

  • 返回 maximum

示例

让我们看看下面的实现以便更好地理解 −

class TreeNode:
   def __init__(self, data):
      self.data = data
      self.left = self.right = None
def solve(root, encode, maxSize, maxNode):
   if (root == None):
      return 0
   left_list = [""]
   right_list = [""]
   ls = solve(root.left, left_list, maxSize, maxNode)
   rs = solve(root.right, right_list, maxSize, maxNode)
   size = ls + rs + 1
   if (left_list[0] == right_list[0]):
      if (size > maxSize[0]):
         maxSize[0] = size
         maxNode[0] = root
   encode[0] = encode[0] + "|" + left_list[0] + "|"
   encode[0] = encode[0] + "|" + str(root.data) + "|"
   encode[0] = encode[0] + "|" + right_list[0] + "|"

   return size

def largestSubtree(node, maxNode):
   maximum = [0]
   encode = [""]
   solve(node, encode, maximum,maxNode)
   return maximum
root = TreeNode(55)
root.left = TreeNode(15)
root.right = TreeNode(70)
root.left.left = TreeNode(10)
root.left.right = TreeNode(25)
root.right.left = TreeNode(75)
root.right.left.left = TreeNode(65)
root.right.left.right = TreeNode(80)
root.right.right = TreeNode(75)
root.right.right.left = TreeNode(65)
root.right.right.right = TreeNode(80)
maxNode = [None]
maximum = largestSubtree(root, maxNode)
print("Root of largest sub-tree",maxNode[0].data)
print("and its size is ", maximum)

输入

root = TreeNode(55)
root.left = TreeNode(15)
root.right = TreeNode(70)
root.left.left = TreeNode(10)
root.left.right = TreeNode(25)
root.right.left = TreeNode(75)
root.right.left.left = TreeNode(65)
root.right.left.right = TreeNode(80)
root.right.right = TreeNode(75)
root.right.right.left = TreeNode(65)
root.right.right.right = TreeNode(80)

输出

Root of largest sub-tree 70
and its size is [7]

相关文章


有用资源