力扣98、530、501-java刷题笔记

一、98. 验证二叉搜索树 - 力扣（LeetCode）

1.1题目

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

节点的左
子树
只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

1.2思路分析

方法一：中序遍历加数组

中序遍历二叉树（递归实现），将遍历后的结果存放到集合中，然后对集合中的元素判断大小

中序遍历二叉树（迭代实现），将遍历后的结果存放到集合中，然后对集合中的元素判断大小

方法二：递归实现

1.3代码实现

方法一：中序遍历加数组（递归）

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
//  方法一定义数组，中序遍历二叉树，将遍历的结果放入到数组中，然后对数组进行比较
class Solution {List<Integer> num = new ArrayList<>();public boolean isValidBST(TreeNode root) {fun(root);for(int i = 0 ;i<num.size()-1 ;i++){if(num.get(i) >= num.get(i+1)) return false;}return true;}public void fun(TreeNode root){if (root == null) return ;if(root.left != null) isValidBST(root.left);num.add(root.val);if(root.right !=  null) isValidBST(root.right);}
}

方法一：中序遍历加数组（迭代）

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
//  迭代法中序遍历
class Solution {public boolean isValidBST(TreeNode root) {if(root == null) return true;Stack<TreeNode> stack = new Stack<>();// 定义一个节点用来存储前序节点TreeNode pre = null;while(root != null || !stack.isEmpty()){while(root!= null){stack.push(root);root = root.left;}TreeNode pop = stack.pop();if(pre!= null && pop.val <= pre.val) return false;pre = pop;root = pop.right;}return true;}
}

方法二：递归实现

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {TreeNode pre = null;public boolean isValidBST(TreeNode root) {if(root == null) return true;boolean left =  isValidBST(root.left);if(!left){return false;}if(pre != null && root.val <= pre.val) return false;pre = root;boolean right =  isValidBST(root.right);return right;}
}

二、530. 二叉搜索树的最小绝对差 - 力扣（LeetCode）

2.1题目

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

示例 1：

输入：root = [4,2,6,1,3]
输出：1

示例 2：

输入：root = [1,0,48,null,null,12,49]
输出：1

2.2思路分析

方法一：中序遍历加数组

方法二：双指针

2.3代码实现

方法一：中序遍历加数组

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {List<Integer> num = new ArrayList<>();public int getMinimumDifference(TreeNode root) {fun(root);int min = num.get(num.size()-1);for(int i = 0 ; i<num.size()-1;i++){min = Math.abs(num.get(i)-num.get(i+1)) < min? Math.abs(num.get(i)-num.get(i+1)):min ; }return min;}public void fun(TreeNode root){if (root == null) return ;if(root.left != null) getMinimumDifference(root.left);num.add(root.val);if(root.right !=  null) getMinimumDifference(root.right);}
}

方法二：双指针

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int min = Integer.MAX_VALUE;TreeNode pre = null;public int getMinimumDifference(TreeNode root) {if(root == null) return 0;fun(root);return min;}public void fun(TreeNode root){if(root ==  null) return ;getMinimumDifference(root.left);if(pre != null){min = Math.min(Math.abs(pre.val - root.val),min);}pre = root;getMinimumDifference(root.right);}
}

三、501. 二叉搜索树中的众数 - 力扣（LeetCode）

3.1题目

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树

示例 1：

输入：root = [1,null,2,2]
输出：[2]

示例 2：

输入：root = [0]
输出：[0]

3.2思路分析

代码随想录 (programmercarl.com)

3.3代码实现

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {// 定义结果数组ArrayList<Integer> resList = new ArrayList<>();// 定义统计次数int count = 0;// 定义最大出现次数int maxCount = 0;// 定义前序指针TreeNode pre = null;public int[] findMode(TreeNode root) {fun(root);int [] result = new int[resList.size()];for(int i = 0 ; i< resList.size();i++){result[i] = resList.get(i);}return result;}public void fun(TreeNode root){if (root == null) return ;fun(root.left);if(pre == null || pre.val != root.val) count=1;else if(pre.val == root.val) count++;if(count > maxCount){maxCount = count;resList.clear();resList.add(root.val);}else if(count == maxCount){resList.add(root.val);}pre = root;fun(root.right);}
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/274734.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！