验证二叉搜索树

客官°小女子只卖身不卖艺 2021-06-22 15:38 375阅读 0赞

> 给定一个二叉树，判断其是否是一个有效的二叉搜索树。  
> 假设一个二叉搜索树具有如下特征：  
> 节点的左子树只包含小于当前节点的数。  
> 节点的右子树只包含大于当前节点的数。  
> 所有左子树和右子树自身必须也是二叉搜索树。  
> 示例 1:  
> 输入:  
> 2  
> /  
> 1 3  
> 输出: true  
> 示例 2:  
> 输入:  
> 5  
> /  
> 1 4  
> /  
> 3 6  
> 输出: false  
> 解释: 输入为: \[5,1,4,null,null,3,6\]。  
> 根节点的值为 5 ，但是其右子节点值为 4 。

链接: [百度百科][Link 1].

*  二叉搜索树  
    1、递归

class Solution { 
    	public boolean isValidBST(TreeNode root) { 
    		return isValid(root, null, null);
    	}
    	// 思想“左子树和右子树都是二叉搜索树”
    	private 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、中序遍历法  
中序遍历是升序

class Solution { 
    
    	private static Integer prev = Integer.MIN_VALUE;
    	private static boolean isValidBST = true;
    
    	public boolean isValidBST(TreeNode root) { 
    		//return isValid(root, null, null);
    		if (root == null || (root.left == null && root.right == null)) return true;
    		inOrder(root);
    		return isValidBST;
    	}
    
    /* private 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); }*/
    
    	private void inOrder(TreeNode root) { 
    		if (root != null) { 
    			inOrder(root.left);
    			if (root.val < prev) { 
    				isValidBST = false;
    				return;
    			}
    			prev = root.val;
    			inOrder(root.right);
    		}
    	}
    }

[Link 1]: https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/7077855?fr=aladdin