java数据结构03
2024-09-04 08:58:00
1.求二叉树的深度
https://www.cnblogs.com/xudong-bupt/p/4036190.html
class TreeNode {
char val;
TreeNode left = null;
TreeNode right = null;
TreeNode(char _val) {
this.val = _val;
}
}
这个可以使用递归，分别求出左子树的深度、右子树的深度，两个深度的较大值+1即可。
// 获取最大深度
public static int getMaxDepth(TreeNode root) {
if (root == null)
return 0;
else {
int left = getMaxDepth(root.left);
int right = getMaxDepth(root.right);
return 1 + Math.max(left, right);
}
}
2.二叉树宽度
使用队列，层次遍历二叉树。在上一层遍历完成后，下一层的所有节点已经放到队列中，此时队列中的元素个数就是下一层的宽度。以此类推，依次遍历下一层即可求出二叉树的最大宽度。
// 获取最大宽度
public static int getMaxWidth(TreeNode root) {
if (root == null)
return 0; Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
int maxWitdth = 1; // 最大宽度
queue.add(root); // 入队 while (true) {
int len = queue.size(); // 当前层的节点个数
if (len == 0)
break;
while (len > 0) {// 如果当前层，还有节点
TreeNode t = queue.poll();
len--;
if (t.left != null)
queue.add(t.left); // 下一层节点入队
if (t.right != null)
queue.add(t.right);// 下一层节点入队
}
maxWitdth = Math.max(maxWitdth, queue.size());
}
return maxWitdth;
}
3.求一个二叉树是否为平衡树
/
* 求树的深度
* @param root
* @return
*/
public static int TreeDepth(BinaryTreeNode root){
if(root == null) {
return 0;
}
int left = TreeDepth(root.left);
int right = TreeDepth(root.right);
return (left > right) ? (left+1) : (right+1);
}
/**
* 一般解法
* @param root
* @return
*/
public static boolean isBalanced(BinaryTreeNode root){
if(root == null) {
return true;
}
int left = TreeDepth(root.left);
int right = TreeDepth(root.right);
int diff = left-right;
if(diff > 1 || diff < -1){
return false;
}
return isBalanced(root.left) && isBalanced(root.right);
}
4.求一个数的平方根
package interview.squareroot;
public class SquareRoot {
public static void main(String[] args) {
double x = 0;
double A = 3;
double eta = 0.001;
while (true) {
double loss = 0.5 * (A - Math.pow(x, 2));
System.out.println("loss:"+loss);
if (loss < 0.001)
break;
x = x + eta * (A - x);
}
System.out.println("3的平方根是" + x);
}
}
最新文章
- 设置table距离顶部位置
- HDU Math Problems
- C++ 创建和遍历二叉树
- pickle 数据对象的序列化和反序列化
- YTU 3022: 完全二叉树（1）
- 解决Android开发中，ActiveAndroid和Gson同时使用，对象序列化失败的问题
- 栈的简单应用 HDU 1022 http://acm.hdu.edu.cn/showproblem.php?pid=1022
- 问题-关于 in []使用过程中报错" Constant expression violates subrange bounds"
- mvn创建web项目
- 一个用UpdateLayeredWindow实现窗体半透明的delphi的代码
- HADOOP在处理HIVE时权限错误的解决办法
- 计划任务可以过UAC？直接添加到计划任务（未经测试）
- PHP学习笔记五【方法】
- android蓝牙的调试（博通蓝牙工作 and 低功耗模式）
- ASP.NET 4.5 Bundle组件（捆绑、缩小静态文件）
- ASP.NET提供三种主要形式的缓存
- 软件包管理之rpm与yum
- [转帖]以Windows服务方式运行ASP.NET Core程序
- Spark SQL内置函数
- Linux命令（十八） 压缩或解压缩文件和目录 gzip gunzip