在二叉树中查找矩阵行元素

Question

我正在尝试编写一个函数，给定一个整数的二叉搜索树 T 和一个整数的矩形矩阵 M，验证是否存在一行 M值属于 T.
这是我的代码：

M = [
    [1, 2, 3],
    [4, 5, 6]
    ]

class Tree:
    def __init__(self, root=None, left=None, right=None):
        self.root = root
        self.left = left
        self.rigth = right

def FindRowInTree(T, M):
    if T is None:
        return False
    else:
        for r in M:
            for e in r:
                if e == T.root and FindRowInTree(T.left, M) is True and FindRowInTree(T.right, M) is True:
                    return True
                FindRowInTree(T.left, M) and FindRowInTree(T.right,M)
        return False

t = Tree(4, Tree(5, None, None), Tree(6, None, None))
x = FindRowInTree(t, M)
print(x)

总是returnsFalse。

我需要更改什么才能使其正常工作？

Answer 1

分解问题。先写一个函数在树中查找单个值：

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
        )

请注意，对于 ordered 二叉树，您可以让该函数根据您要查找的值与根值；这就是“二进制搜索”。但是，由于您的树是无序的，您只需要在每个节点搜索两个子节点，这意味着您正在遍历整棵树。

无论如何，一旦你有了一个查找单个值的函数，你需要做的就是在循环中调用它：

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)

在二叉树中查找矩阵行元素

Find matrix row elements in a binary tree

python

binary-search-tree