LeetCode刷题—二叉搜索树的套路

本文针对BST 的基础操作：判断 BST 的合法性（98）、增（701）、删（450）、查（700）。以几道题来总结出套路模板，以一敌十！
98，验证二叉搜索树，medium
700，二叉搜索树中的搜索，easy
701，二叉搜索树中的插入操作，medium
450，删除二叉搜索树中的节点，medium

98，验证二叉搜索树，medium

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

• 方法一：递归。

  • 思路：很容易想到对于节点root，采用递归判断左子节点的值比它小，右子节点的值比它大，但注意：对每个节点都满足也不一定是BST树，如：

        5
       / \
      1   6
         / \
        4   7
    

    没有满足右子树的节点都比root值大。

    建立辅助函数，增加最小节点min和最大节点max 作为辅助函数的参量。对于root，比较root.val与当前的min.val 和 max.val，再对root.left 和root.right 进行递归操作。

  • 代码：

    class Solution {	
    	public boolean isValidBST(TreeNode root) {
            return healper(root, null, null);
        }
        //是BST树必须满足 min.val < root.val < max.val
        public boolean healper(TreeNode root, TreeNode min, TreeNode max){
            if(root == null) return true;
            if(min != null && min.val >= root.val) return false;
            if(max != null && max.val <= root.val) return false;
        //左子树范围的最小值是min.val，最大值是当前节点的值，也就是root的值，因为左子树的值要比当前节点小
        //右子数范围的最大值是max.val，最小值是当前节点的值，也就是root的值，因为右子树的值要比当前节点大
            return healper(root.left, min, root) && healper(root.right, root, max);
        }
    }