我回答这个面试挑战对吗?(在C#中检查有效的二进制树)

本文关键字：有效 检查 二进制 挑战 面试 回答这个 | 更新日期: 2023-09-27 18:22:26

我是C#的初学者。让我知道我是否正确回答了这个面试问题（面试结束了，所以不要认为你在帮我作弊或其他什么）。

提示是

编写一个函数来确定给定的二叉树integers是一个有效的二进制搜索树。假设每个节点包含一个指向其左边子项的指针，一个指向它右边子项的指示器，以及整数，但不是指向其父级的指针。你可以使用任何语言你喜欢。但是，如果您的语言已经有库，则可能没有使用那些库。

public class node
{
    node left { get; set; }
    node right { get; set; }
    int val;
}

（我写的上面的内容正确吗？因为node是class，所以我的left和right是对node的引用，即内存地址的副本。对吗？）

bool IsValidBT ( node N, HashSet<int> H ) 
{
    // function is initially called on the root node with an
    // empty HashSet<int> and is recursively called on 
    // the children, checking for any repeats in which case
    // the tree would be invalid
    if (  H.Contains(N.val) ) return false;
    else  H.Add(N.val);
   if ( left != null && !IsValidBT(left) ) return false;
   if ( right != null && !IsValidBT(right) ) return false; 
   return true; // if made it here, still valid  
}

好的，提示说不使用库，但我认为这意味着不使用任何提供一线解决方案的库。当然，我至少需要标准库。但是，上述逻辑有错吗？二叉树有没有可能是无效的，除非它以某种方式包含重复的值？

我回答这个面试挑战对吗?(在C#中检查有效的二进制树)

这似乎更适合codereview.stackeexchange.com。但答案很简单，所以…

最重要的是，没有。你没有正确回答这个问题。最明显的缺陷是代码无法编译。您已经声明了一个方法IsValidBT(node, HashSet<int>)，但在调用它时，只传递一个参数。这行不通。

也不清楚你是否正确理解了这个问题。你似乎关心数据中是否有重复。但是a）从提示中还不清楚这是否会被禁止，并且b）

正如评论中所指出的，你可以在维基百科上找到一个二进制搜索树验证（或验证）的经典实现：二进制搜索树-验证。这里显示的C++算法的C#版本，使用node数据结构，可能看起来像这样：

bool IsBST(node n, int minKey, int maxKey)
{
    if (n == null) return true;
    // Assumes that equal valued children are placed to the left
    if (n.val <= minKey || n.val > maxKey) return false;
    return IsBST(n.left, minKey, n.val) && IsBST(n.right, n.val, maxKey);
}

这样调用：

IsBST(rootNode, int.MinValue, int.MaxValue);

相关文章：