- 700. 二叉搜索树中的搜索">700. 二叉搜索树中的搜索
- 98. 验证二叉搜索树">98. 验证二叉搜索树
- 530. 二叉搜索树的最小绝对差">530. 二叉搜索树的最小绝对差
- 501. 二叉搜索树中的众数">501. 二叉搜索树中的众数
- 236. 二叉树的最近公共祖先">236. 二叉树的最近公共祖先
- 235. 二叉搜索树的最近公共祖先">235. 二叉搜索树的最近公共祖先
- 701. 二叉搜索树中的插入操作">701. 二叉搜索树中的插入操作
- 450. 删除二叉搜索树中的节点">450. 删除二叉搜索树中的节点
- 669. 修剪二叉搜索树">669. 修剪二叉搜索树
- 538. 把二叉搜索树转换为累加树">538. 把二叉搜索树转换为累加树
有序二叉树的中序遍历就是一个单调递增的数组!!!
搜索一条边的写法：
if (递归函数(root->left)) return ;if (递归函数(root->right)) return ;
搜索整个树写法：
left = 递归函数(root->left);
right = 递归函数(root->right);
left与right的逻辑处理;
700. 二叉搜索树中的搜索
/**
* 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 TreeNode searchBST(TreeNode root, int val) {
if (root == null) {
return null;
}
//单层逻辑
if (root.val > val) {
return searchBST(root.left, val);
}
if (root.val < val) {
return searchBST(root.right, val);
}
return root;
}
}
98. 验证二叉搜索树
/**
* 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 (pre != null && pre.val >= root.val){//中
return false;
}
pre = root;// 更新前一个节点
boolean right = isValidBST(root.right);//右
return left && right;
}
}
530. 二叉搜索树的最小绝对差
那么二叉搜索树采用中序遍历，其实就是一个有序数组。
在一个有序数组上求两个数最小差值，这是不是就是一道送分题了。
/**
* 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;//前驱
int result = Integer.MAX_VALUE;
private void traversal(TreeNode root){
if (root == null) return;
traversal(root.left);//左
if (pre != null){
result = Math.min(result,root.val - pre.val);//中
}
pre = root;//前驱赋值
traversal(root.right);//右
}
public int getMinimumDifference(TreeNode root) {
traversal(root);
return result;
}
}
501. 二叉搜索树中的众数
暴力法
class Solution {
public int[] findMode(FindModeInBinarySearchTree.TreeNode root) {
Map<Integer, Integer> map = new HashMap<>();
List<Integer> list = new ArrayList<>();
if (root == null) return list.stream().mapToInt(Integer::intValue).toArray();
// 获得频率 Map
searchBST(root, map);
List<Map.Entry<Integer, Integer>> mapList = map.entrySet().stream()
.sorted((c1, c2) -> c2.getValue().compareTo(c1.getValue()))
.collect(Collectors.toList());
list.add(mapList.get(0).getKey());
// 把频率最高的加入 list
for (int i = 1; i < mapList.size(); i++) {
if (mapList.get(i).getValue() == mapList.get(i - 1).getValue()) {
list.add(mapList.get(i).getKey());
} else {
break;
}
}
return list.stream().mapToInt(Integer::intValue).toArray();
}
void searchBST(FindModeInBinarySearchTree.TreeNode curr, Map<Integer, Integer> map) {
if (curr == null) return;
map.put(curr.val, map.getOrDefault(curr.val, 0) + 1);
searchBST(curr.left, map);
searchBST(curr.right, map);
}
}
搜索二叉树中序遍历有序特性来写
/**
* 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> result = new ArrayList<>();
int maxCount;//最大频率
int count;//统计频率
TreeNode pre;//前驱
private void searchBST(TreeNode cur){
if (cur == null) return;
searchBST(cur.left);//左
if (pre == null){//说明是第一个节点
count = 1;
}else if (pre.val == cur.val){//与前一个节点值相同
count++;
}else {//与前一个节点值不相同
count = 1;//重置
}
pre = cur;//更新前驱
if (count == maxCount){//如果和最大值相同，则刚入result
result.add(cur.val);
}
if (count > maxCount){//如果计数大于最大频率
maxCount = count;//更新
result.clear();//清除result，因为现在最大的已经不是之前的max了
result.add(cur.val);
}
searchBST(cur.right);//右
}
public int[] findMode(TreeNode root) {
searchBST(root);
int[] res = new int[result.size()];
for (int i = 0; i < res.length; i++) {
res[i] = result.get(i);
}
return res;
}
}
236. 二叉树的最近公共祖先
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) { // 递归结束条件
return root;
}
// 后序遍历
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left == null && right == null) { // 若未找到节点 p 或 q
return null;
}else if(left == null && right != null) { // 若找到一个节点
return right;
}else if(left != null && right == null) { // 若找到一个节点
return left;
}else { // 若找到两个节点
return root;
}
}
}
235. 二叉搜索树的最近公共祖先
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private TreeNode traversal(TreeNode cur,TreeNode p,TreeNode q){
//终止条件
if (cur == null) return cur;
//单层递归
if (cur.val > p.val && cur.val > q.val){//都在左子树
TreeNode left = traversal(cur.left, p, q);
if (left != null){
return left;
}
}else if (cur.val < p.val && cur.val < q.val){//都在右子树
TreeNode right = traversal(cur.right, p, q);
if (right != null){
return right;
}
}else {
return cur;//在两棵子树
}
return cur;
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
return traversal(root,p,q);
}
}
701. 二叉搜索树中的插入操作
其实就是在空姐点插入val根本不需要改变树形
/**
* 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 TreeNode insertIntoBST(TreeNode root, int val) {
//终止条件
// 如果当前节点为空，也就意味着val找到了合适的位置，此时创建节点直接返回。
if (root == null){
TreeNode node = new TreeNode(val);
return node;
}
//单层递归逻辑
if (root.val > val){
//// 递归创建左子树
root.left = insertIntoBST(root.left, val);
}
if (root.val < val){
//// 递归创建右子树
root.right = insertIntoBST(root.right, val);
}
return root;
}
}
450. 删除二叉搜索树中的节点
这就涉及改变树形状了
/**
* 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 TreeNode deleteNode(TreeNode root, int key) {
//终止条件
if (root == null) return root;
if (root.val == key){//找到节点
//左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
if (root.left == null && root.right == null){
return null;
}else if (root.left == null && root.right != null){//左为空，右不为空 返回root。right
return root.right;
}else if (root.left != null && root.right == null){//左bu为空，右为空 返回root。left
return root.left;
}else if (root.left != null && root.right != null){
TreeNode cur = root.right;
while (cur.left != null){
cur = cur.left;
}
cur.left = root.left;
return root.right;
}
}
if (root.val > key){
root.left = deleteNode(root.left,key);
}
if (root.val < key){
root.right = deleteNode(root.right,key);
}
return root;
}
}
669. 修剪二叉搜索树
/**
* 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 {
// 定义：删除 BST 中小于 low 和大于 high 的所有节点，返回结果 BST
public TreeNode trimBST(TreeNode root, int low, int high) {
if (root == null) return null;
if (root.val < low) {
// 直接返回 root.right
// 等于删除 root 以及 root 的左子树
return trimBST(root.right, low, high);
}
if (root.val > high) {
// 直接返回 root.left
// 等于删除 root 以及 root 的右子树
return trimBST(root.left, low, high);
}
//接下来要将上一层处理完左子树的结果赋给root->left，
//处理完右子树的结果赋给root->right。
//最后返回root节点，代码如下：
root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);
return root;
}
}
538. 把二叉搜索树转换为累加树
class Solution {
public TreeNode convertBST(TreeNode root) {
traverse(root);
return root;
}
// 记录累加和
int sum = 0;
void traverse(TreeNode root) {
if (root == null) {
return;
}
traverse(root.right);
// 维护累加和
sum += root.val;
// 将 BST 转化成累加树
root.val = sum;
traverse(root.left);
}
}
// 详细解析参见：
// https://labuladong.github.io/article/?qno=538
若有收获，就点个赞吧
0 人点赞
