Implement a function to check if a binary tree is a binary search tree.
Example 1:
Input: 2 / \ 1 3 Output: true
Example 2:
Input: 5 / \ 1 4 / \ 3 6 Output: false Explanation: Input: [5,1,4,null,null,3,6]. the value of root node is 5, but its right child has value 4.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
res, t = True, None
def isValidBST(self, root: TreeNode) -> bool:
self.isValid(root)
return self.res
def isValid(self, root):
if not root:
return
self.isValid(root.left)
if self.t is None or self.t < root.val:
self.t = root.val
else:
self.res = False
return
self.isValid(root.right)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private boolean res = true;
private Integer t = null;
public boolean isValidBST(TreeNode root) {
isValid(root);
return res;
}
private void isValid(TreeNode root) {
if (root == null) {
return;
}
isValid(root.left);
if (t == null || t < root.val) {
t = root.val;
} else {
res = false;
return;
}
isValid(root.right);
}
}
- Non-recursive in-order traversal
func isValidBST(root *TreeNode) bool {
stack := make([]*TreeNode, 0)
var prev *TreeNode = nil
node := root
for len(stack) > 0 || node != nil {
for node != nil {
stack = append(stack, node)
node = node.Left
}
node = stack[len(stack)-1]
stack = stack[:len(stack)-1]
if prev == nil || node.Val > prev.Val {
prev = node
} else {
return false
}
node = node.Right
}
return true
}
- Use upper bound and lower bound to check
func isValidBST(root *TreeNode) bool {
return check(root, math.MinInt64, math.MaxInt64)
}
func check(node *TreeNode, lower, upper int) bool {
if node == nil {
return true
}
if node.Val <= lower || node.Val >= upper {
return false
}
return check(node.Left, lower, node.Val) && check(node.Right, node.Val, upper)
}