c# - 二叉搜索树验证

Question

感谢您阅读我的主题。我正在 Test Dome 练习一些 C#。我目前正在尝试编写的练习如下: http://www.testdome.com/Questions/Csharp/BinarySearchTree/484?testId=21&testDifficulty=Hard

我目前的结果:

• 案例:正确答案
• 简单案例:正确答案
• 一般情况:错误答案
• 边缘情况:错误答案
• 性能测试:错误答案

您可以在下面阅读我到目前为止编写的代码。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;

public class Node
{
    public int Value { get; set; }                      // Value of {node} == integer (1,2,3,4,5)
    public Node Left { get; set; }                      // Reference to left node (n1, n2, n3) == Node.
    public Node Right { get; set; }                     // Reference to right node (n1, n2, n3) == Node.
    public Node(int value, Node left, Node right)       
    {
        Value = value;                                  // (int)
        Left = left;                                    // (node)
        Right = right;                                  // (node)
    }
}

public class BinarySearchTree
{
    public static bool IsValidBST(Node root)
    {
        if (root.Left == null && root.Right == null)
            return true;

        else if (root.Left == null)
        {
            // Checking root.Right.Value
            if (root.Value <= root.Right.Value)
                return true;

            else
                return false;
        }
        else if (root.Right == null)
        {
            // Checking root.Left.Value
            if (root.Value > root.Left.Value)
                return true;
            else
                return false; 
        }
        else
        {
            // Checking both Values
            if (root.Value > root.Left.Value && root.Value <= root.Right.Value)
                return true;
            else
                return false;
        }
    }


    public static void Main(string[] args)
    {
        Node n1 = new Node(1, null, null);
        Node n3 = new Node(3, null, null);
        Node n2 = new Node(2, n1, n3);

        // Execute function and write it to the console
        Console.WriteLine(IsValidBST(n2));
        Console.ReadLine();
    }
}

我不知道如何实现才能通过测试。我不希望您提供书面代码，而是提供有关练习的更多信息。请记住，我当前的代码远非整洁。谢谢大家。

Answer 1

您没有检查所有上层节点值。你应该有所有上层节点的数组/列表，所以你可以检查它。

而且你还应该使用递归调用。像这样

IsValidBST(Node root, List<int> upperValues = null) 
{
 ... 
 bool childIsValid = IsValidBST (root.Left, upperValuesLeft ) && IsValidBST(root.Right, upperValuesRight )
}