在Python中找到给定树中最大二叉搜索子树的程序
假设我们有一个二叉树,我们必须找到最大子树(具有最大节点数)作为二叉搜索树。
因此,如果输入如下:
那么输出将是
要解决此问题,我们将按照以下步骤执行-
- max_size := [0]
- max_node := [null]
- 定义一个函数遍历(traverse())。这将接受节点
- 如果节点为空,那么
- 返回null
- left := traverse(node的左子树)
- right := traverse(node的右子树)
- lst := left + [节点值] + right
- 如果lst已排序,则
- 如果max_size[0] < lst的大小,那么
- max_size[0] := lst的大小
- max_node[0] := node
- 如果max_size[0] < lst的大小,那么
- 返回lst
- traverse(root)
- 从主方法返回max_node[0]
更多Python相关文章,请阅读:Python 教程
示例(Python)
让我们看一下以下实现,以更好地理解-
class TreeNode:
def __init__(self, data, left = None, right = None):
self.val = data
self.left = left
self.right = right
def print_tree(root):
if root is not None:
print_tree(root.left)
print(root.val, end = ', ')
print_tree(root.right)
class Solution:
def solve(self, root):
max_size = [0]
max_node = [None]
def traverse(node):
if not node:
return []
left = traverse(node.left)
right = traverse(node.right)
lst = left + [node.val] + right
if sorted(lst) == lst:
if max_size[0] < len(lst):
max_size[0] = len(lst)
max_node[0] = node
return lst
traverse(root)
return max_node[0]
ob = Solution()
root = TreeNode(12)
root.left = TreeNode(3)
root.right = TreeNode(5)
root.right.left = TreeNode(4)
root.right.right = TreeNode(6)
print_tree(ob.solve(root))
输入
root = TreeNode(12)
root.left = TreeNode(3)
root.right = TreeNode(5)
root.right.left = TreeNode(4)
root.right.right = TreeNode(6)
输出
4, 5, 6,