98.validate-binary-search-tree.java

import java.util.*;

/*
 * @lc app=leetcode id=98 lang=java
 *
 * [98] Validate Binary Search Tree
 *
 * https://leetcode.com/problems/validate-binary-search-tree/description/
 *
 * algorithms
 * Medium (27.73%)
 * Likes:    4048
 * Dislikes: 542
 * Total Accepted:    712.1K
 * Total Submissions: 2.6M
 * Testcase Example:  '[2,1,3]'
 *
 * 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.
 * 
 * 
 * 
 * 
 * Example 1:
 * 
 * 
 * ⁠   2
 * ⁠  / \
 * ⁠ 1   3
 * 
 * Input: [2,1,3]
 * Output: true
 * 
 * 
 * Example 2:
 * 
 * 
 * ⁠   5
 * ⁠  / \
 * ⁠ 1   4
 * / \
 * 3   6
 * 
 * Input: [5,1,4,null,null,3,6]
 * Output: false
 * Explanation: The root node's value is 5 but its right child's value is 4.
 * 
 * 
 */

// @lc code=start
/**
 * Definition for a binary tree node. public class TreeNode { int val; TreeNode
 * left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left
 * = left; this.right = right; } }
 */
class Solution {
	public boolean isValidBST(TreeNode root) {
		if (root == null)
			return true;
		List<Integer> result = new ArrayList<>();
		preOrder(root, result);
		for (int i = 0; i < result.size() - 1; i++) {
			if (i + 1 < result.size()) {
				if (result.get(i) >= result.get(i + 1))
					return false;
			}
		}
		return true;
	}

	public void preOrder(TreeNode root, List<Integer> result) {
		if (root.left != null)
			preOrder(root.left, result);
		result.add(root.val);
		if (root.right != null)
			preOrder(root.right, result);
	}
}
// @lc code=end
// []
// [1]
// [4,1,5,null,null,4,6]