二叉树validate-binary-search-tree-leetcode练习题

野性酷女 2023-07-23 03:58 69阅读 0赞

import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.LinkedList;
    import java.util.Queue;
    
    /**
     * 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
     *
     * 假设一个二叉搜索树具有如下特征：
     *
     *     节点的左子树只包含小于当前节点的数。
     *     节点的右子树只包含大于当前节点的数。
     *     所有左子树和右子树自身必须也是二叉搜索树。
     *
     * 示例 1:
     *
     * 输入:
     *     2
     *    / \
     *   1   3
     * 输出: true
     *
     * 示例 2:
     *
     * 输入:
     *     5
     *    / \
     *   1   4
     *      / \
     *     3   6
     * 输出: false
     * 解释: 输入为: [5,1,4,null,null,3,6]。
     *      根节点的值为 5 ，但是其右子节点值为 4 。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/validate-binary-search-tree
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    class Solution {
    
        /**
         * 递归求解
         *
         * @param root
         * @return
         */
        public boolean isValidBST(TreeNode root) {
            return validateCore(root, Long.MIN_VALUE, Long.MAX_VALUE);
        }
    
        private boolean validateCore(TreeNode node, Long lower, Long upper) {
            if (node == null) {
                return true;
            }
            long currentValue = node.val;
            if (currentValue <= lower || currentValue >= upper) {
                return false;
            }
            return validateCore(node.left, lower, currentValue) && validateCore(node.right, currentValue, upper);
        }
    
    }
    
    public class MainClass {
        public static TreeNode stringToTreeNode(String input) {
            input = input.trim();
            input = input.substring(1, input.length() - 1);
            if (input.length() == 0) {
                return null;
            }
    
            String[] parts = input.split(",");
            String item = parts[0];
            TreeNode root = new TreeNode(Integer.parseInt(item));
            Queue<TreeNode> nodeQueue = new LinkedList<>();
            nodeQueue.add(root);
    
            int index = 1;
            while (!nodeQueue.isEmpty()) {
                TreeNode node = nodeQueue.remove();
    
                if (index == parts.length) {
                    break;
                }
    
                item = parts[index++];
                item = item.trim();
                if (!item.equals("null")) {
                    int leftNumber = Integer.parseInt(item);
                    node.left = new TreeNode(leftNumber);
                    nodeQueue.add(node.left);
                }
    
                if (index == parts.length) {
                    break;
                }
    
                item = parts[index++];
                item = item.trim();
                if (!item.equals("null")) {
                    int rightNumber = Integer.parseInt(item);
                    node.right = new TreeNode(rightNumber);
                    nodeQueue.add(node.right);
                }
            }
            return root;
        }
    
        public static String booleanToString(boolean input) {
            return input ? "True" : "False";
        }
    
        public static void main(String[] args) throws IOException {
            BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
            String line;
            while ((line = in.readLine()) != null) {
                TreeNode root = stringToTreeNode(line);
                boolean ret = new Solution().isValidBST(root);
                String out = booleanToString(ret);
                System.out.print(out);
            }
        }
    }

public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    
        TreeNode(int x) {
            val = x;
        }
    }

实现思想：

递归