【算法】【二叉树模块】求二叉树中最大搜索二叉子树,返回头结点
前言
当前所有算法都使用测试用例运行过,但是不保证100%的测试用例,如果存在问题务必联系批评指正~
在此感谢左大神让我对算法有了新的感悟认识!
问题介绍
原问题
求二叉树中最大的二叉子树
如图所示二叉树:
该二叉树的最大搜索二叉子树结构为:
返回节点6即可
解决方案
1、后续遍历二叉树
2、每一次的遍历都返回四个信息:
· 当前节点为根节点的子树中最大的搜索二叉树
· 当前节点为根节点的子树中最大搜索二叉树的节点个数
· 当前节点为根节点的子树中最大值
· 当前节点为根节点的子树中最小值
3、返回上一层时判断当前节点为根节点的子树是否是搜索二叉树,如果是,则将信息更新后返回上一层,如果不是则判断左右子树谁size更大,谁就是当前的最大搜索子树,更新record返回上一层即可.
代码编写
java语言版本
public static MyTreeNode getBST(MyTreeNode root){
if (root == null){
return null;
}
int[] record = new int[3];
return process(root, record);
}
/**
* 每一个节点遍历都要返回四个数据:
* 1、以该节点为root的最大搜索二叉树节点的root节点
* 2、搜索二叉子树节点数量
* 3、搜索二叉子树的最大值
* 4、搜索二叉子树的最小值
* @param root
* @param record
* @return
*/
private static MyTreeNode process(MyTreeNode root, int[] record) {
if (root == null){
record[0] = 0;
record[1] = Integer.MIN_VALUE;
record[2] = Integer.MAX_VALUE;
return null;
}
MyTreeNode leftMaxRoot = process(root.getLeft(), record);
int leftSize = record[0];
int leftMax = record[1];
int leftMin = record[2];
MyTreeNode rightMaxRoot = process(root.getRight(), record);
int rightSize = record[0];
int rightMax = record[1];
int rightMin = record[2];
if (leftMaxRoot == root.getLeft() && rightMaxRoot == root.getRight()
&& leftMax < root.getData() && rightMin > root.getData()){
// 自己就是一颗二叉树
record[0] = leftSize + rightSize + 1;
record[1] = rightMax == Integer.MIN_VALUE ? root.getData() : rightMax;
record[2] = leftMin == Integer.MAX_VALUE ? root.getData() : leftMin;
return root;
}else {
// 比较左边和右边哪个大
if (leftSize >= rightSize){
record[0] = leftSize;
record[1] = leftMax;
record[2] = leftMin;
return leftMaxRoot;
}else{
record[0] = rightSize;
record[1] = rightMax;
record[2] = rightMin;
return rightMaxRoot;
}
}
}
public static void main(String[] args) {
MyTreeNode root = CommonUtils.getSearchMyTreeNode();
MyTreeNode node1 = new MyTreeNode(1);
MyTreeNode node9 = new MyTreeNode(9);
node1.setRight(root);
node1.setLeft(node9);
PrintTreeDirect.myPrint(node1);
getBST(node1);
}
c语言版本
正在学习中
c++语言版本
正在学习中
思考感悟
1、思路来源
二叉树中用得最多的思想就是将同一个问题通过递归“问到”每一个子树,怎么理解这句话呢?当前问题就是求二叉树中最大搜索二叉子树,那么把这个问题问到每一个子树,以该题为例,首先问到1问子树9和子树6是否存在最大搜索二叉子树,9和6判断自己是否能够成为最大子树跟自己判断是否能够成为最大子树是一样的逻辑,因此自己需要什么信息,9和6就需要什么信息,那么1需要9中最大子树的头结点并且还要知道节点数(第二个信息),知道以后还要判断自己是否也能成为最大子树,所以需要9提供最大值(第三个信息)和最小值(第四个信息),6也是同理
2、注意要点:
这里需要注意一下null的返回判断,如果遍历到null时,说明null值天然支持父节点成为二叉子树,因此节点数为0,最大值尽可能的小,最小值尽可能的大,让父节点符合条件。
写在最后
方案和代码仅提供学习和思考使用,切勿随意滥用!如有错误和不合理的地方,务必批评指正~
如果需要git源码可邮件给2260755767@qq.com
再次感谢左大神对我算法的指点迷津!
相关文章
- 98. 验证二叉搜索树
- 安卓手机便签模糊搜索历史内容怎么实现?
- 织梦搜索指定多个栏目的文档
- 解决Select2控件不能在jQuery UI Dialog中不能搜索的bug
- 算法练习之将有序数组转换为二叉搜索树,平衡二叉树
- 每日一道 LeetCode (24):将有序数组转换为二叉搜索树
- 8-crm项目-kingadmin,列表页---搜索
- deepin v20.4设置全局搜索的快捷键
- CentOS 文本搜索grep
- atitit.vod search doc.doc 点播系统搜索功能设计文档
- 机器学习(十七):网格搜索(Grid Search)和SVM
- 具有自适应搜索策略的灰狼优化算法-附代码
- 剑指 Offer 54. 二叉搜索树的第k大节点
- 240. 搜索二维矩阵 II-暴力解法和单调性扫描
- 面试题 10.03. 搜索旋转数组
- Linux中搜索命令find
- 【CSS】课程网站头部制作 ④ ( 搜索栏按钮测量 | 搜索栏按钮代码编写 | 代码示例 )
- L34.linux命令每日一练 -- 第五章 Linux信息显示与搜索文件命令 -- echo和watch
- vue监听手机键盘搜索事件
- 第五章 搜索技术