Validate Binary Search Tree

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(H) 递归栈空间

思路

递归的判断每个节点是否满足BST的要求，需要注意的是BST的要求不只是左节点小于根节点小于右节点，还有个隐含的条件是，左子树里所有节点都要小于根节点，而右子树里所有节点都要大于根节点。所以我们要把这个上限和下限代入递归中。

代码

public class Solution {    public boolean isValidBST(TreeNode root) {        return root == null ? true : helper(root, null, null);    }        public boolean helper(TreeNode root, Integer max, Integer min){        boolean left = true, right = true;        // 如果该节点大于上限 返回假        if(max != null && root.val >= max){return false;        }        // 如果该节点小于下限 返回真        if(min != null && root.val <= min){return false;        }        // 判断左节点和左子树是否都符合BST要求        if(root.left != null) left = root.left.val < root.val && helper(root.left, root.val, min);        // 判断右节点和右子树是否都符合BST要求        if(root.right != null) right = root.right.val > root.val && helper(root.right, max, root.val);        return left && right;    }}