脚本宝典收集整理的这篇文章主要介绍了Validate Binary Search Tree leetcode，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
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.
递归法
思路
遍历树, 用数组保存之前访问的节点, 如果之前访问的都小于当前访问的值那么树就是合理树
复杂度
时间 O(n) 空间 递归栈O(log)
代码
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
ArrayList<Integer> cur = new ArrayList<Integer>();
cur.add(null);
return helper(cur, root);
}
public boolean helper(ArrayList<Integer> cur, TreeNode root) {
if (root == null) {
return true;
}
boolean left = helper(cur, root.left);
if (cur.get(0) != null) {
if (cur.get(0) >= root.val) {
return false;
}
}
cur.set(0, root.val);
boolean right = helper(cur, root.right);
return left && right;
}以上是脚本宝典为你收集整理的Validate Binary Search Tree leetcode全部内容，希望文章能够帮你解决Validate Binary Search Tree leetcode所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。