LeetCode刷题Day16——二叉搜索树（搜索、验证、最小绝对差、众数）

/**
 * <pre>
 * 1.递归
 * 2.迭代
 * </pre>
 *
 * @author <a href="https://github.com/Ken-Chy129">Ken-Chy129</a>
 * @date 2023/1/17 14:33
 */
public class 二叉搜索树中的搜索700 {
    public static TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }
        if (val < root.val) {
            return searchBST(root.left, val);
        } else {
            return searchBST(root.right, val);
        }
    }
    public static TreeNode searchBST2(TreeNode root, int val) {
        while (root != null) {
            if (root.val == val) {
                return root;
            } else if (val < root.val) {
                root = root.left;
            } else {
                root = root.right;
            } 
        }
        return null;
    }
}

/**
 * <pre>
 * 1.递归，每次判断根据上下限判断当前节点是否满足条件
 * 2.中序遍历：二叉搜索树中序遍历后的顺序为从小到大
 * </pre>
 *
 * @author <a href="https://github.com/Ken-Chy129">Ken-Chy129</a>
 * @date 2023/1/17 16:21
 */
public class 验证二叉搜索树98 {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    public boolean isValidBST(TreeNode node, long lower, long upper) {
        if (node == null) {
            return true;
        }
        if (node.val >= upper || node.val <= lower) {
            return false;
        }
        return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
    }
    public boolean isValidBST2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        long inorder = Long.MIN_VALUE;
        while (!stack.empty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode pop = stack.pop();
            if (pop.val <= inorder) { // 二叉搜索树中序遍历的节点应该越来越大
                return false;
            }
            inorder = pop.val;
            root = pop.right;
        }
        return true;
    }
}

/**
 * <pre>
 * 1.中序遍历，出来的结果是升序排序，插值最小肯定存在在两个相邻元素之间
 * </pre>
 *
 * @author <a href="https://github.com/Ken-Chy129">Ken-Chy129</a>
 * @date 2023/1/17 16:58
 */
public class 二叉搜索树的最小绝对差530 {
    public int getMinimumDifference(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        long last = Integer.MIN_VALUE, ans = Integer.MAX_VALUE;
        while (!stack.empty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode pop = stack.pop();
            ans = Math.min(ans, pop.val - last);
            last = pop.val;
            root = pop.right;
        }
        return (int)ans;
    }
}

/**
 * <pre>
 * 1.中序遍历
 * </pre>
 *
 * @author <a href="https://github.com/Ken-Chy129">Ken-Chy129</a>
 * @date 2023/1/17 17:29
 */
public class 二叉搜索树中的众数501 {
    public int[] findMode(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();
        int maxCount = 0, count = 0, last = Integer.MIN_VALUE;
        while (!stack.empty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode pop = stack.pop();
            if (last == pop.val) {
                count++;
            } else {
                count = 1;
            }
            if (maxCount == count) {
                list.add(pop.val);
            } else if (maxCount < count) {
                list.clear();
                list.add(pop.val);
                maxCount = count;
            }
            last = pop.val;
            root = pop.right;
        }
        int[] res = new int[list.size()];
        for (int i=0; i<list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}