q98_验证二叉搜索树_LeetCode题目分类与面试问题整理

q98_验证二叉搜索树

1

package 二叉搜索树相关.q98_验证二叉搜索树.f1;
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

package 二叉搜索树相关.q98_验证二叉搜索树.f1;
import java.util.ArrayList;
import java.util.List;
/**
 * 递归的中序遍历（二叉搜索树的中序遍历是有序的）o(n)
 */
public class Solution {
    List<Integer> rs = new ArrayList<>();
    private List<Integer> ldr(TreeNode root) {
        if (root == null) {
            return rs;
        }
        ldr(root.left);
        rs.add(root.val);
        ldr(root.right);
        return rs;
    }
    public boolean isValidBST(TreeNode root) {
        ldr(root);
        if (rs.size() < 2) {
            return true;
        }
        int a = rs.get(0);
        for (int i = 1; i < rs.size(); i++) {
            if (rs.get(i) <= a) {
                return false;
            }
            a = rs.get(i);
        }
        return true;
    }
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(4);
        root.left = n1;
        root.right = n2;
        TreeNode n3 = new TreeNode(3);
        TreeNode n4 = new TreeNode(6);
        n2.left = n3;
        n2.right = n4;
        System.out.println(new Solution().isValidBST(root));
    }
}

2

package 二叉搜索树相关.q98_验证二叉搜索树.f2;
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

package 二叉搜索树相关.q98_验证二叉搜索树.f2;
/**
 * 寻找上下界递归 o(n)
 */
public class Solution {
    public boolean valid(TreeNode root, Integer min, Integer max) {
        if (root == null) {
            return true;
        }
        int val = root.val;
        if (min != null && val <= min) {
            return false;
        }
        if (max != null && val >= max) {
            return false;
        }
        if (!valid(root.left, min, val)) {
            return false;
        }
        if (!valid(root.right, val, max)) {
            return false;
        }
        return true;
    }
    public boolean isValidBST(TreeNode root) {
        return valid(root, null, null);
    }
}

3

package 二叉搜索树相关.q98_验证二叉搜索树.f3;
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

package 二叉搜索树相关.q98_验证二叉搜索树.f3;
import java.util.LinkedList;
import java.util.Queue;
/**
 * 层序遍历迭代法判断上下界 o(n)
 */
public class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        Queue<Integer> min = new LinkedList<>();
        Queue<Integer> max = new LinkedList<>();
        while (!queue.isEmpty()) {
            TreeNode temp = queue.poll();
            Integer maxt = max.poll();
            Integer mint = min.poll();
            if (mint != null && temp.val <= mint) {
                return false;
            }
            if (maxt != null && temp.val >= maxt) {
                return false;
            }
            if (temp.left != null) {
                min.add(mint);
                max.add(temp.val);
                queue.add(temp.left);
            }
            if (temp.right != null) {
                max.add(maxt);
                min.add(temp.val);
                queue.add(temp.right);
            }
        }
        return true;
    }
    public static void main(String[] args) {
        TreeNode root = new TreeNode(10);
        TreeNode n1 = new TreeNode(5);
        TreeNode n2 = new TreeNode(15);
        root.left = n1;
        root.right = n2;
        TreeNode n3 = new TreeNode(6);
        TreeNode n4 = new TreeNode(20);
        n2.left = n3;
        n2.right = n4;
        System.out.println(new Solution().isValidBST(root));
    }
}