一开始想到使用中序遍历解决
- 即中序遍历必须是升序
- 但是需要额外的变量记录先前遍历到的值(在整数的范围内题目数据范围限制不可以取一个特殊的值)
可以考虑换种思路。 采用先序遍历的想法:
- 遍历到一个结点,首先查看当前结点是否在给定范围内
- 置这个给定范围最小值为这个遍历到的结点,最大值不变,遍历右子树
- 置这个给定范围最小值不变,最大值为遍历到的结点,遍历左子树
AC代码(借鉴别人的)
class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBST(root, Long.MIN_VALUE);
}
public boolean isValidBST(TreeNode node, long lower) {
if (node == null) {
return true;
}
if (node.val <= lower || node.val >= upper) {
return false;
}
return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
}
}
|