转载

[LeetCode] 98. Validate Binary Search Tree 验证二叉搜索树 leetcode java

题目:

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

<strong>输入:</strong>
    2
   / /
  1   3
<strong>输出:</strong> true

示例 2:

<strong>输入:
</strong>    5
   / /
  1   4
     / /
    3   6
<strong>输出:</strong> false
<strong>解释:</strong> 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

思路：

二叉查找树有一个重要的性质：即中序遍历递增（不存在两个节点值相等），根据此，中序遍历完成后，查看序列是否有序即可知道是否是二叉查找树。

代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
		ArrayList<Integer> pre = new ArrayList<Integer>();
		pre.add(null);
		return helper(root, pre);
	}

	private boolean helper(TreeNode root, ArrayList<Integer> pre) {
		if (root == null)
			return true;

		boolean left = helper(root.left, pre);

		if (pre.get(pre.size() - 1) != null && root.val <= pre.get(pre.size() - 1))
			return false;
		pre.add(root.val);
		boolean right = helper(root.right, pre);
		return left && right;
	}
}

原文 http://www.lisite.top/2018/07/14/leetcode-98-validate-binary-search-tree-验证二叉搜索树-leetcode-java/556.html

正文到此结束