h5响应式网站源码/个人网页设计作品模板

题目：给定一棵树，判断是否是合法的二叉搜索树。
如果合法返回true，不合法则返回false。

首先，应该明确二叉搜索树的定义，二叉搜索树是一个递归的定义，即二叉搜索树的左子节点小于根节点，而右节点大于根节点，同时左右子树也是一棵二叉搜索树。

错误的想法：
先判断根节点和左右子节点的大小关系，如果不符合大小关系，直接返回false。如果符合，则递归调用判断左右子树是否合法。
如下：

/**
* 验证是否是合法二叉搜索树*/
public boolean isValidBST(TreeNode root) {if (root == null) {return true;}// 判断根节点与左子节点的关系boolean isLeftValid = true;if (root.left != null) {isLeftValid = root.val > root.left.val;}// 判断根节点与右子节点的关系boolean isRightValid = true;if (root.right != null) {isRightValid = root.val < root.right.val;}// 左子点及右子节点递归调用，判断是否符合这种大小关系return isLeftValid && isRightValid && isValidBST(root.left) && isValidBST(root.right);
}

这种想法只考虑了根节点与其左右子节点的关系，即只考虑了每三个节点之前的大小关系，而没有考虑子节点与所有剩余子节点的大小关系。
如对于如下的二叉树则会得到错误结果:

				41			60	    2     3		7

这棵二叉树很显然不是二叉搜索树，因为其中的3小于4。

正确的解法一

/**
* 验证是否是合法二叉搜索树
*/
public boolean isValidBST(TreeNode root) {return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}/**
* 当前root值的上下界要在指定的范围内
* @param root
* @param lower 下界
* @param upper 上界 
* @return
*/
public boolean isValidBST(TreeNode root, long lower, long upper) {if (root == null) {return true;}// 不符合搜索树的定义if (root.val <= lower || root.val >= upper) {return false;}return isValidBST(root.left, lower, root.val) && isValidBST(root.right, root.val, upper);
}

正确的解法二：

// 用long型的数据来记录前一个节点，int型过不了leetcode测试用例
long pre = Long.MIN_VALUE;
/*** @param root* @return 本质上还是利用了中序的排序性质，只是用了递归的方式。*/
public boolean isValidBST(TreeNode root) {if (root == null) {return true;}// 先递归判断左子树是否合法if (!isValidBST(root.left)) {return false;}// 在判断当前节点与左子节点的大小关系if (root.val <= pre) {return false;}pre = root.val;// 在判断右子树是否合法return isValidBST(root.right);
}

正确的解法三：
利用二叉搜索树的中序遍历有序性，边遍历边比较。

/*** 在遍历的过程中比较， 在leetcode上这种方式的时间还没有上面的递归调用快。 */
public boolean isValidBST3(TreeNode root) {if (root == null) {return true;}Deque<TreeNode> stack = new ArrayDeque<TreeNode>();TreeNode cur = root;// stack是空的，故加入cur不为空的判断while (!stack.isEmpty() || cur != null) {while (cur != null) {stack.push(cur);cur = cur.left;}TreeNode tmp = stack.pop();if (tmp.val <= pre) {return false;} else {pre = tmp.val;}cur = tmp.right;// 这里不能在push了，因为cur在while循环开头就会push，如果这里push就会push两次了。 // if (cur != null) {// stack.push(cur);// }}return true;
}