Validate Binary Search Tree (M)
題目
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
Example 1:
2
/ \
1 3
Input: [2,1,3]
Output: true
Example 2:
5
/ \
1 4
/ \
3 6
Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
題意
判斷給定樹是否為二叉查找樹(左/右子樹為嚴格小于/大于關系)，
思路
第一時間想到遞回判斷左結點小于根結點、右結點大于根結點，但這種做法是錯誤的，因為可能出現以下這種情況(因為只考慮了左子樹根結點小于根節點，實際上要保證左子樹所有結點都小于根節點，右子樹同理)：
由BST的性質-中序遍歷必然得到遞增序列，因而可以通過中序遍歷給定二叉樹，判斷序列是否遞增對來判斷是否是BST，中序遍歷方法較多，具體可參考 94. Binary Tree Inorder Traversal，
另一種方法：對第一種方法進行改進，加上最小值、最大值的限定，使得當前結點都必須在(min, max)的范圍里，因為測驗樣例包含了Integer.MAX_VALUE和Integer.MIN_VALUE，所以范圍端點要使用long(硬要用int可以再設兩個引數minUsed和maxUsed來標記Integer邊界值是否已被使用)，
代碼實作
Java
范圍限制
class Solution {
public boolean isValidBST(TreeNode root) {
return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean isValid(TreeNode x, long minValue, long maxValue) {
if (x == null) {
return true;
}
if (x.val >= maxValue || x.val <= minValue) {
return false;
}
return isValid(x.left, minValue, x.val) && isValid(x.right, x.val, maxValue);
}
}
中序遍歷
class Solution {
int pre;
boolean isFirst;
public boolean isValidBST(TreeNode root) {
isFirst = true;
return isValid(root);
}
private boolean isValid(TreeNode x) {
if (x == null) {
return true;
}
// 處理左子樹
if (!isValid(x.left)) {
return false;
}
// 處理當前結點
if (!isFirst && x.val <= pre) {
return false;
}
if (isFirst) {
isFirst = false;
}
pre = x.val;
// 處理右子樹
if (!isValid(x.right)) {
return false;
}
return true;
}
}
JavaScript
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isValidBST = function (root) {
return isValid(root, [-Infinity, Infinity])
}
let isValid = function (root, range) {
if (!root) {
return true
}
if (root.val >= range[1] || root.val <= range[0]) {
return false
}
return isValid(root.left, [range[0], root.val]) && isValid(root.right, [root.val, range[1]])
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/235923.html
標籤：其他
上一篇：編譯安裝msyql