//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.

//

//

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

*/

package com.llz.algorithm.algorithm2019.secondweek;

import com.llz.algorithm.algorithm2019.firstweek.TreeNode;

import java.util.ArrayList;

import java.util.List;

public class LeetCode_98_2 {

/**

* Hard to think, referenced from solution.

* @param root

* @return

*/

public boolean isValidBSTByTraverse(TreeNode root) {

return judgeValidBSt(root, null, null);

}

public boolean judgeValidBSt(TreeNode cur, TreeNode lower, TreeNode upper) {

if (cur == null) return true;

if (lower != null && cur.val <= lower.val) return false;

if (upper != null && cur.val >= upper.val) return false;

if (!judgeValidBSt(cur.right, cur, upper)) return false;

if (!judgeValidBSt(cur.left, lower, cur)) return false;

return true;

}

private List<Integer> list = new ArrayList<>();

/**

* Use inOrder traverse, both of time complexity and space complexity is O(n).

*

* @param root

* @return

*/

public boolean isValidBST(TreeNode root) {

getListByInOrderTraverse(root);

for (int i = 1; i < list.size(); i++) {

if (list.get(i) <= list.get(i - 1))

return false;

}

return true;

}

public void getListByInOrderTraverse(TreeNode root) {

if (root == null) return;

getListByInOrderTraverse(root.left);

list.add(root.val);

getListByInOrderTraverse(root.right);

}

}