数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程语言
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究如何使用 C# 中的递归检查二叉树是否为有效的二叉搜索树？
如果一棵树的所有左子树上的元素都比该结点小，而所有右子树上的元素都比该结点大，则这棵树为二叉搜索树。我们首先检查该节点是否含有任何值，如果该结点为空，则我们认为其为有效的二叉搜索树，并返回 true。在检查节点是否为空后，我们通过传递节点、最小值和最大值来调用递归方法 isValidBST。如果根节点值小于最小值，或者根节点值大于最大值，我们认为其不是二叉搜索树，并返回 false，否则，我们通过传递左值和右值递归调用 isValidBST 方法，直到它检查所有节点
示例
public class TreesPgm{
public class Node{
public int Value;
public Node LeftChild;
public Node RightChild;
public Node(int value){
this.Value = value;
}
public override String ToString(){
return "Node=" + Value;
}
}
public bool isValidBST(Node root){
if (root == null){
return true;
}
return isValidBST(root, int.MinValue, int.MaxValue);
}
private bool isValidBST(Node root, int min, int max){
if (root == null){
return true;
}
if (root.Value <= min || root.Value >= max){
return false;
}
return isValidBST(root.LeftChild, min, root.Value) && isValidBST(root.RightChild,
root.Value, max);
}
}输入
5 2 6 1 3
输出
True
更新于: 17-Aug-2021
344 次浏览
广告