描述
給定一個二叉樹脆烟，判斷其是否是一個有效的二叉搜索樹。
假設(shè)一個二叉搜索樹具有如下特征：
節(jié)點的左子樹只包含小于當前節(jié)點的數(shù)硝桩。
節(jié)點的右子樹只包含大于當前節(jié)點的數(shù)煤痕。
所有左子樹和右子樹自身必須也是二叉搜索樹。
解題思路
1.中序遍歷數(shù)候衍，結(jié)果必然是升序。
//用于記錄前一個值
private Integer last;
//中序遍歷樹洒放，比較值蛉鹿。時間復雜度:O(n)，空間復雜度:O(n)往湿。
public boolean isValidBST(TreeNode root)
{
if (root == null) return true;
if (!isValidBST(root.left)) return false;
if (last != null && root.val <= last) return false;
last = root.val;
if (!isValidBST(root.right)) return false;
return true;
}
2.遍歷樹的同時指定上下限范圍妖异，每個節(jié)點取值范圍是上下界，左節(jié)點的上界值是父節(jié)點领追，右節(jié)點的下界值是父節(jié)點他膳。適合所有遍歷方式。
//層序遍歷樹绒窑，上下界比較值棕孙。時間復雜度:O(n)，空間復雜度:O(n)。
public boolean isValidBST3(TreeNode root)
{
if (root == null) return true;
Queue<TreeNode> nodes = new LinkedList<>();
Queue<Integer> mins = new LinkedList<>();
Queue<Integer> maxs = new LinkedList<>();
nodes.offer(root);
mins.offer(null);
maxs.offer(null);
while (!nodes.isEmpty()) {
TreeNode node = nodes.poll();
Integer min = mins.poll();
Integer max = maxs.poll();
if (min != null && node.val <= min) return false;
if (max != null && node.val >= max) return false;
if (node.left != null) {
nodes.offer(node.left);
mins.offer(min);
maxs.offer(node.val);
}
if (node.right != null) {
nodes.offer(node.right);
mins.offer(node.val);
maxs.offer(max);
}
}
return true;
}
