把问题分解成碎片。首先编写一个函数,在树中查找单个值:
class Tree:
def __init__(self, root=None, left=None, right=None):
self.root = root
self.left = left
self.right = right
def __contains__(self, value):
return (
self.root == value
or self.left is not None and value in self.left
or self.right is not None and value in self.right
)
请注意,使用
命令
二叉树,你可以让它只检查左或右,这取决于你要查找的值与根值的比较;这就是“二进制搜索”。不过,由于你的树是无序的,你只需要在每个节点上搜索两个子节点,这意味着你要遍历整个树。
在任何情况下,一旦您有了一个查找单个值的函数,您所需要做的就是在循环中调用它:
def find_row_in_tree(tree, matrix):
return any(
all(i in tree for i in row)
for row in matrix
)
如果你想以一种更有效的方式做到这一点,无序的二叉树对你没有任何好处;我只想写一个实用函数,把它转换成更有用的东西,比如
set
:
def tree_to_set(tree):
if tree is None:
return set()
return {tree.root} | tree_to_set(tree.left) | tree_to_set(tree.right)
def find_row_in_tree(tree, matrix):
tree_as_set = tree_to_set(tree)
return any(tree_as_set.issuperset(row) for row in matrix)
