LeetCode-Validate Binary Search Tree

川长思鸟来 2022-08-04 00:59 13阅读 0赞

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.

难度不大，关键是能用多种方法解决之。

可以先按其本身的定义来解决此题：左子树的所有节点小于此节点，右子树的所有节点都大于此节点。当然还需要两个辅助方法，我称之为树的工具类方法，求最大值和最小值。

public boolean isValidBST(TreeNode root) {
            return root == null || (root.left == null ? true : root.val > max(root.left)) && 
            		(root.right == null ? true : root.val < min(root.right)) && 
            		isValidBST(root.left) && 
            		isValidBST(root.right);
        }
        
        public int max(TreeNode root) {
        	if (root == null) return Integer.MIN_VALUE;
        	return Math.max(Math.max(max(root.left), max(root.right)), root.val);
        }
        
        public int min(TreeNode root) {
        	if (root == null) return Integer.MAX_VALUE;
        	return Math.min(Math.min(min(root.left), min(root.right)), root.val);
        }

第二种方式是稍微转变一下可知，中序遍历BST，得到的是排序序列，所以就有了如下方法：

public boolean isValidBST(TreeNode root) {
            List<Integer> ret = new ArrayList<Integer>();
            dfs(root, ret);
            for (int i = 0; i < ret.size()-1; i++) {
                if (ret.get(i) >= ret.get(i+1)) return false;
            }
            return true;
        }
        private void dfs(TreeNode root, List<Integer> ret) {
            if (root == null) return;
            dfs(root.left, ret);
            ret.add(root.val);
            dfs(root.right, ret);
        }

从上述两种方法，都不止一次遍历。所以肯定要思考有没有遍历一次就可以得出结论的，上代码：

private TreeNode pre = null;
        public boolean isValidBST(TreeNode root) {
            if (root == null)
            	return true;
            if (!isValidBST(root.left)) 
            	return false;
            if (prev != null && prev.val >= root.val) return false;
            prev = root;
            return isValidBST(root.right);
        }

在遍历的过程中，记录前驱节点，在与本节点比较即可判断。

在遍历过程中可以进行很多改造，也就是改造遍历可以得出很多高效的算法！！！最后一种方法值得回味。