98. Validate Binary Search Tree

98. Validate Binary Search Tree

判断树是不是 binary search tree

A valid 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.

My Solutions:

验证搜做二叉树:

1. 如果是中序遍历,验证搜索二叉树,需要验证遍历结果是否为单调升序。

2. 对于先序遍历,常规做法是需要维持一个单调递减栈用来存储根节点的,不然没办法准确地获取每颗子树的根节点。极限做法是不开辟额外占空间,将原始的遍历结果作为栈,这样就是常数空间的做法。

3. 对于后序遍历,相应的,维持一个单调递增栈用来保存每颗子树的根节点。

方法1：recursive

用min和max代表一个node.val需要限制的范围

public boolean isValidBST(TreeNode root) {
        return isValid(root, null, null);
}

public boolean isValid(TreeNode root, Integer min, Integer max) {
    if(root == null) return true;
    if(min != null && root.val <= min) return false;
    if(max != null && root.val >= max) return false;
    
    return isValid(root.left, min, root.val) && isValid(root.right, root.val, max);
}

方法2：用stack 做dfs

用inorder traverse tree. 先到最左边的leaf node，更新一个最小值(pre = left node)。然后stack会pop出这个node的root，比较此root和pre的大小，更新pre。接着到此root的右边，比较右边和pre的大小。

/**
 * 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) {
        if (root == null) return true;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        
        while (root != null || !stack.isEmpty()) {
            while (root != null){
                stack.push(root);
                root = root.left; // inorder
            }
            root = stack.pop(); // this is the left more node
            if (pre != null && pre.val >= root.val) return false;
            pre = root;
            root = root.right;
        }
        
        return true;
    }
}