這是我檢查一棵樹是否是 BST 的嘗試：
public boolean isBST() {
return isBSTRecursively(this.root, new Max());
}
class Max {
int value;
}
private boolean isBSTRecursively(Node node, Max max) {
if (node == null) return true; // to handle null root
// to handle scenario when both child nodes are absent
if(node.getLeft() == null && node.getRight() == null) {
max.value = node.getValue();
return true;
}
// if left child is absent, we only investigate right subtree
if(node.getLeft() == null) {
Max rightMax = new Max();
boolean isRightBST = isBSTRecursively(node.getRight(), rightMax);
max.value = Math.max(node.getValue(), rightMax.value);
if(isRightBST && node.getValue() < rightMax.value) {
return true;
} else {
return false;
}
} else {
Max leftMax = new Max();
boolean isLeftBST = isBSTRecursively(node.getLeft(), leftMax);
// if right child is absent, we only investigate left subtree
if(node.getRight() == null) {
max.value = Math.max(node.getValue(), leftMax.value);
if(isLeftBST && node.getValue() > leftMax.value) {
return true;
} else {
return false;
}
} else {
// we investigate both left and right subtrees
Max rightMax = new Max();
boolean isRightBST = isBSTRecursively(node.getRight(), rightMax);
max.value = Math.max(Math.max(leftMax.value, node.getValue()), rightMax.value);
if(isLeftBST && isRightBST && leftMax.value < node.getValue() && node.getValue() < rightMax.value) {
return true;
} else {
return false;
}
}
}
在使用多個測驗用例進行測驗時，代碼運行良好。
但我不確定這是否是一個好的、干凈的方法。
遞回方法似乎很大。我正在分別處理空左節點、空右節點、節點本身為空、兩個子節點都為空等場景。我想它們都可以以更小、更清潔的方式處理。
此外，我總是更傾向于迭代方法（我通常發現它更好地可視化）。這里會更好嗎（考慮到它可以迭代地完成）？
有什么建議？
uj5u.com熱心網友回復：
更簡潔的遞回方法
您可以使用有界方法，即每次遞回都有兩個變數：min和max.
最初
min = INT_MIN和max = INT_MAXif
node = NULLthen 回傳 True 因為空的 BST 是 BSTelse 檢查如果
node.val < min or node.val > max這個條件是Truethen 樹不是 BST，return False注意：嚴格的不等式>和<用作 BST 不允許重復元素。左遞回：
recur(node.left)保持min不變，max = node.val - 1因為左子樹的值不應大于node.val - 1。max不能是node.val因為 BST 不能有重復的元素。將布爾回傳值存盤在say中left右遞回：
recur(node.right)保持min = node.val 1不變max。右子樹的值應不小于
node.val 1。將布爾回傳值存盤在say中right回傳
left && right
uj5u.com熱心網友回復：
@Aditya 提供了更優雅的解決方案的成分。
通常不禁止二叉搜索樹具有重復值，因此不應將“視窗”減少為 1。
這是建議的代碼：
public boolean isBST() {
return isBSTRecursively(this.root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private boolean isBSTRecursively(Node node, int min, int max) {
return node == null
|| node.getValue() >= min && node.getValue() <= max
&& isBSTRecursively(node.getLeft(), min, node.getValue())
&& isBSTRecursively(node.getRight(), node.getValue(), max);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/438328.html
上一篇：Python集未檢測到重復節點