algorithm - 我怎么知道这个矩阵是二叉搜索树还是二叉树。

Question

我正在尝试回答以下问题，但我不太确定矩阵是二叉搜索树还是二叉树。有什么方法可以告诉吗？

在二叉搜索树上找到两个节点之间的最小公共(public)祖先。最不共同的祖先是距离作为两个节点的祖先的根最远的节点。例如，根是树上所有节点的共同祖先，但如果两个节点都是根的左 child 的后代，那么左 child 可能是最低的共同祖先。您可以假设两个节点都在树中，并且树本身遵守所有 BST 属性。函数定义应类似于问题 4(T, r, n1, n2)，其中 T 是表示为矩阵的树，其中列表的索引等于存储在该节点中的整数，1 表示子节点， r是表示根的非负整数，n1和n2是表示不分先后的两个节点的非负整数。例如，一个测试用例可能是

question4([[0, 1, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[1, 0, 0, 0, 1],
[0, 0, 0, 0, 0]],
3,
1,
4)

Answer 1

我认为，矩阵表示如下图:

矩阵应如下所示:

0 1 0 0 0
0 0 0 0 0
0 0 0 0 0
1 0 0 0 1
0 0 0 0 0

行 0 代表节点 0。它在索引 1 处有一个 1，即节点 1 是节点 0 的子节点。同样的方法应该适用于其他行。例如。节点 0 和节点 4 是节点 3 的子节点。

要检查图是否为树，请执行以下操作:树中的每个节点(根节点除外)都只有一个父节点。因此，您需要确保矩阵中的所有列都恰好有一个 1 条目(根列除外，它应该没有 1 条目)。

要检查树是否为二叉树，您需要检查一个节点是否最多有两个子节点。您可以通过检查每一行是否最多有两个 1 条目来做到这一点。

要检查二叉树是否为二叉搜索树，您必须检查每个子树中是否至多有一个子树。 IE。在 i 行中，[0 .. i-1] 中最多有一个 1 条目，并且最多有一个 条目 [i+1 .. n-1] 中的 1 条目。正如灰 mustache 指出的那样，这个条件是不充分的，因为它不考虑更高级别的祖先。要检查这一点，您需要构建树并从根遍历到叶子，检查节点是否落在允许的间隔内。