zj

前言

又是学习LeetCode二叉树的新一天，今天主要来学习一下二叉搜索树的内容，希望博主记录的内容能够对大家有所帮助，一起加油吧朋友们！💪💪💪

二叉搜索树中的搜索

LeetCode题目链接

需要在给定的二叉搜索树（BST）中找到节点值为给定的整数值val的节点，返回以该节点为根的子树，节点不存在返回null

1727573389701

我们来梳理思路🤔🤔🤔

首先的话二叉搜索树的定义，二叉搜索树就是左子树的节点的值都比根节点的值要小，反之右子树的节点是值都比根节点的值要大
就每次判断当前节点的val是否为给定的val吧，不是的话就递归左右子树，逻辑比较简单🤔🤔🤔

直接来梳理递归三要素

确定递归的参数和返回值

1 2	//要求返回树的根节点，然后的话传入搜索树的根节点和一个要去找的val public TreeNode searchBST(TreeNode root, int val) {}

确定递归的出口

1 2	//递归要叶子节点仍要进行单层逻辑判断故最后的递归是会到叶子节点的子节点，所以这里是直接判断root为null if(root == null) return null; //递归出口

确定递归的单层处理逻辑

//单层处理逻辑
if(root.val == val) return root;

//递归处理左右子树
TreeNode leftResult = searchBST(root.left, val);
if(leftResult != null) return leftResult; //找到了
TreeNode rightResult = searchBST(root.right, val);
return rightResult; //直接返回右边查询的结果

这里的迭代法我们不需要借助栈或者是队列来存储节点，因为二叉搜索树的话我们判断一个节点的值和目标值对比后我们就知道去往它的左子树还是右子树去搜索了，所以不需要来存储多余的处理节点🤔🤔🤔

/**递归法 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while(root != null){
            if(root.val == val)return root;
            if(root.val > val){//往左树去查
                root = root.left;
            }else{
                root = root.right;
            }
        }
        return null;
    }
    
}

验证二叉搜索树

判断一个给定的二叉树是否是二叉搜索树

1727575363450

首先给出博主写的一个错误示例，从中我们可以更好的分析出递归的三要素

/**递归法 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        //递归出口，递归的目的是为了找false的情况，遍历到叶子节点即可
        if(root.left == null && root.right == null) return true;

        //处理单层逻辑
        if(root.left.val > root.val || root.right.val < root.val) return false;

        //递归处理左右子树
        boolean left = isValidBST(root.left);
        if(!left)return false;
        return isValidBST(root.right);
    }
}

这里存在一个比较明显的问题，就是当我的单层处理逻辑以为是每层判断左右子节点的值不符合范围就返回false，但是实际上每层满足左小右大，整体的二叉树不一定满足左小有大

1727578478682

所以我们需要调整单层处理逻辑，对于每个节点的判断应该去判断节点值和其上层的节点（上几层未知）的值进行判断，这也表示递归会进入到叶子节点的空节点进行判断，所以我们调整递归三要素如下🤔🤔🤔

确定递归的参数和返回值

1
2

//以两个参数要记录要比较的上层节点的值，两个值分别对左右子树的节点进行一个范围限制
private boolean isValidBST(TreeNode root, Integer maxValue, Integer minValue){}

确定递归的出口

1	if(root == null)return true; //都递归处理到这一层了说明检查的没问题返回true

确定单层处理逻辑

1
2
3

if((maxValue != null && root.val >= maxValue) ||(minValue != null && root.val <= minValue))return false;

        return isValidBST(root.left, root.val, minValue) && isValidBST(root.right, maxValue, root.val);

递归的完整代码如下：

/**递归法 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, null, null);
    }
    private boolean isValidBST(TreeNode root, Integer maxValue, Integer minValue){
        if(root == null)return true; //都递归处理到这一层了说明检查的没问题返回true

        if((maxValue != null && root.val >= maxValue) ||(minValue != null && root.val <= minValue))return false;

        return isValidBST(root.left, root.val, minValue) && isValidBST(root.right, maxValue, root.val);
    }
}

迭代方法的话我们也来进行迭代关键点分析🤔🤔🤔

栈初始化

// 使用栈来保存待处理的节点以及它们各自的有效值范围（左树就是最大值限制，右树就是最小值限制）
Stack<Object[]> stack = new Stack<>();
//将根节点及其初始的有效值范围添加到栈中。初始范围可以是(null, null)，这表示没有边界限制
stack.push(new Object[] {root, null, null}); // 节点，最大值，最小值

节点处理逻辑

Object[] cur = stack.pop();
TreeNode node = (TreeNode) cur[0]; // 当前检查的节点
Integer maxValue = (Integer) cur[1]; // 当前节点的最大值
Integer minValue = (Integer) cur[2]; // 当前节点的最小值

if (node == null) continue; // 递归出口

if ((maxValue != null && node.val >= maxValue) || (minValue != null && node.val <= minValue)) {
    return false;    // 逻辑检查，值不在范围内
}

// 更新范围并将子节点入栈
stack.push(new Object[] {node.left, node.val, minValue}); // 左子树
stack.push(new Object[] {node.right, maxValue, node.val}); // 右子树

完整迭代代码如下：

/**迭代法 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        Stack<Object[]> stack = new Stack<>();
        stack.push(new Object[] {root, null, null}); // 节点，最大值，最小值

        while (!stack.isEmpty()) {
            Object[] cur = stack.pop();
            TreeNode node = (TreeNode) cur[0]; // 当前检查的节点
            Integer maxValue = (Integer) cur[1]; // 当前节点的最大值
            Integer minValue = (Integer) cur[2]; // 当前节点的最小值

            if (node == null) continue; // 递归出口

            if ((maxValue != null && node.val >= maxValue) || (minValue != null && node.val <= minValue)) {
                return false;    // 逻辑检查，值不在范围内
            }

            // 更新范围并将子节点入栈
            stack.push(new Object[] {node.left, node.val, minValue}); // 左子树
            stack.push(new Object[] {node.right, maxValue, node.val}); // 右子树
        }

        return true; // 全部节点检查通过
    }
}

二叉搜索树的最小绝对差

LeetCode题目链接

给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。

1727594047229

我们梳理下逻辑🤔🤔🤔

因为对于二叉搜索树的任何节点，所有左子树的节点小于它，而右子树的节点大于它，根据这个特性可以很方便地找到相邻节点的差值🤔
中序遍历结合二叉搜索树会使得按照节点值升序来对每个节点进行访问，这个过程中可以用一个变量来跟踪前一个节点值，然后用一个变量来存储最小差值，每次访问进行更新🤔

梳理完毕后我们来梳理递归三要素

确定递归的参数和返回值

1
2
3

private Integer prev = -1; //用全局变量记录前一个节点值，这里全局变量不受规模问题影响，提高代码可读性
private int min = Integer.MAX_VALUE;//用全局变量记录最小差值，递归处理每个节点进行更新
private void inOrderTraversal(TreeNode root){}

确定递归的出口

1 2	//很明显到叶子节点时还要继续更新最小差值即会进入到空节点的递归处理 if(root == null) return;

确定递归的单层处理逻辑

//中序遍历先处理左子树
inOrderTraversal(root.left);

//处理当前节点
if(prev != null){
    min = Math.min(min, Math.abs(root.val - prev));
}
prev = root.val;//更新前一个节点的值

//中序遍历后处理右子树
inOrderTraversal(root.right);

递归完整代码如下

/*递归法*/
class Solution {
    private int prev = -1; //前一个节点值
    private int min = Integer.MAX_VALUE;//最小差值
    public int getMinimumDifference(TreeNode root) {
        inOrderTraversal(root);
        return min;
    }

    private void inOrderTraversal(TreeNode root){
        if(root == null) return;

        //中序遍历先处理左子树
        inOrderTraversal(root.left);

        //处理当前节点
        if(prev != -1){
            min = Math.min(min, Math.abs(root.val - prev));
        }
        prev = root.val;//更新前一个节点的值

        //中序遍历后处理右子树
        inOrderTraversal(root.right);
    }
}

我们继续来梳理迭代的思路🤔🤔🤔

用栈来进行节点遍历
仍然用两个变量来进行前序节点值记录和最小差值记录

/*迭代法*/
class Solution {
    public int getMinimumDifference(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        int prev = -1; //前一个节点值
        int min = Integer.MAX_VALUE;//最小差值

        //中序遍历
        while(!stack.isEmpty() || cur != null){
            //将左子树的所有节点入栈
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }

            //处理栈顶节点
            cur = stack.pop();
            if (prev != -1) {
                min = Math.min(min, Math.abs(cur.val - prev));
            }
            prev = cur.val; // 更新前一个节点的值

            // 转到右子树
            cur = cur.right;
        }
        return  min;

    }


}

总结

今天就先学到这里，国庆假期越来越近，继续加油👊👊👊

前言

二叉搜索树中的搜索

验证二叉搜索树

二叉搜索树的最小绝对差

总结

Copyright © 2020 | Author: 周建 | Theme By Coder