我是否正确回答了这个面试挑战？（在 C# 中检查有效的二叉树）

Question

我是 C# 的初学者。如果我做对了这个面试题，请告诉我（面试已经结束，所以不要以为你在帮我作弊或其他什么）。

提示是

Write a function to determine whether a given binary tree of distinct integers is a valid binary search tree. Assume that each node contains a pointer to its left child, a pointer to its right child, and an integer, but not a pointer to its parent. You may use any language you like.However, if your language already has libraries, you may not use those libraries.

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

(我上面写的关于如何根据提示创建节点是否正确？因为node是一个class，我的left和right 是对 nodes 的引用，即内存地址的副本。对吧？）

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  
}

好的，提示说不使用库，但我认为它们的意思是不使用任何提供 1-line 解决方案的库。当然，我至少需要标准库。但是上面的逻辑有什么问题吗？有什么方法可以使二叉树无效，除非它以某种方式包含重复值？

Answer 1

这似乎更适合 codereview.stackexchange.com。但是回答起来很简单，所以…

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

也不清楚您是否正确理解了问题。您似乎担心数据中是否存在重复。但是 a) 从提示中不清楚甚至不允许这样做，并且 b) 二叉树无效的更明显原因是数据是否未按有序方式组织（例如，如果父项左侧的数字大于父项的值）。

如评论中所述，您可以在维基百科上找到二叉搜索树验证（或验证）的经典实现：Binary search tree - Verification。此处显示的 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);

我是否正确回答了这个面试挑战？（在 C# 中检查有效的二叉树）

Did I answer this interview challenge right? (Checking for valid binary tree in C#)

.net

c#

algorithm

tree

data-structures

我是否正确回答了这个面试挑战？ （在 C# 中检查有效的二叉树）

Did I answer this interview challenge right? (Checking for valid binary tree in C#)

.net

c#

algorithm

tree

data-structures

我是否正确回答了这个面试挑战？（在 C# 中检查有效的二叉树）