当前位置:网站首页>leetcode二叉树系列(一)
leetcode二叉树系列(一)
2022-08-04 09:03:00 【你食不食油饼】
目录
1、对称二叉树
题目描述:
思路:要判断二叉树是否是对称二叉树,对称二叉树的条件大家得看清 是要root.left.right = root.right.left,我开始就吃了亏,没审清题,以为是要左节点等于左节点,右节点等于右节点;
这道题比较简单,我们直接进入代码:
public boolean isSymmetric(TreeNode root) {
return dfs(root.left,root.right);
}
public boolean dfs(TreeNode left,TreeNode right){
if(left == null && right == null) return true;
if(left == null || right == null) return false;
if( left.val != right.val) return false;
return (dfs(left.left,right.right) && dfs(left.right,right.left));
}
2、二叉树的层序遍历
题目描述:
思路:层序遍历就是遍历二叉树时,从第一层依次遍历到第二层再到第三层,与我们往常的前序、中序、后序遍历不同;
BFS(广度优先遍历),就是专门用于进行层序遍历的搜索算法,所以这道题我们会采用bfs来进行二叉树的层序遍历
代码如下:
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> lists = new ArrayList<>();
if (root == null) return lists;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
//size为每一层节点的个数
int size = queue.size();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
list.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
lists.add(list);
}
return lists;
}
3、二叉树的最大深度
题目描述:
思路:就是做一个递归操作,很简单,直接看代码
public int maxDepth(TreeNode root) {
if(root == null) return 0;
return Math.max(root.left == null ? 0 : maxDepth(root.left),
root.right == null ? 0 : maxDepth(root.right)) + 1;
}
4、从前序和中序遍历构造二叉树
题目描述:
思路: 前序遍历数组[3,9,20,15,7],中序遍历数组[9,3,15,20,7],进行递归操作
第一次递归,建立val为3的节点root,我们找到它在中序遍历数组中出现的位置,
root.left =[9],root.right = [20,15,7]
第二次递归,建立val为9的节点root,此时回退,返回root;
第三次递归,建立val为20的节点root,我们依然找到它在中序遍历数组出现的位置,
root.left = [15],root.right = [7]
第四次递归,建立val为15的节点root,此时回退,返回root;
第五次递归,建立val为7的节点root,此时回退,返回root;
第五次递归结束时,此时回退完成后,二叉树就已经建立完毕
至于我们判断回退的条件,我们可以递归参数中加入preStart、preEnd表示在前序数组中的开始索引位置和结束索引位置,当preStart == preEnd时,退出此次递归;
进入代码:
public TreeNode buildTree(int[] preorder, int[] inorder) {
LinkedHashMap<Integer,Integer> map = new LinkedHashMap<>();
return build(preorder,0,preorder.length,inorder,0,inorder.length);
}
public TreeNode build(int[] preorder,int preStart,int preEnd,int[] inorder,int inStart,int inEnd){
if(preStart == preEnd) return null;
int rootVal = preorder[preStart];
//每一个节点都是他子节点的主节点
TreeNode root = new TreeNode(rootVal);
int index = inStart;
for(;index < inEnd;index++){
if(rootVal == inorder[index])
break;
}
//移动了多少个位置才到达主节点
int leftnum = index - inStart;
root.left = build(preorder,preStart+1,preStart+leftnum+1,inorder,inStart,index);
root.right = build(preorder,preStart+leftnum+1,preEnd,inorder,index+1,inEnd);
return root;
}
持续更新中~~
边栏推荐
- It is found that several WRH tables are locked, what should I do?
- Anton Paar安东帕密度计比重计维修DMA35性能参数
- Occupy, fill in later
- Get the number of cpu cores
- MATLAB/Simulink快捷键
- ZbxTable 2.0 重磅发布!6大主要优化功能!
- GBsae 8c 数据库使用中报错,肿么办?
- 【论文笔记】Understanding Long Programming Languages with Structure-Aware Sparse Attention
- Wang Shuang's Assembly Language Chapter 4: The First Program
- 字符串与正则表达式(C#)
猜你喜欢
随机推荐
layout manager
binder通信实现
sql在字段重复时 对某个字段根据最新时间取数
【NOI模拟赛】纸老虎博弈(博弈论SG函数,长链剖分)
Grafana9.0发布,Prometheus和Loki查询生成器、全新导航、热图面板等新功能!
About Oracle RAC 11g rebuilding the disk group
Oracle怎么获取当前库或者同一台服务器上某几个库的数据总行数?
关于#sql#的问题:后面换了一个数据库里面的数据就不能跑了
预测性维护学习之路
MATLAB绘图总结
【论文笔记】Dynamic Convolution: Attention over Convolution Kernels
RL学习笔记(一)
TiDB升级与案例分享(TiDB v4.0.1 → v5.4.1)
.NET深入解析LINQ框架(五:IQueryable、IQueryProvider接口详解)
户外徒步旅行
思想茶叶蛋 (Jul 31,2022)| 元宇宙(Metaverse)下了一枚什么样的蛋
LVGL的多语言转换工具--字体设置的好助手
DNS 查询原理详解—— 阮一峰的网络日志
cannot import name 'import_string' from 'werkzeug' [bug solution]
下午14:00面试,14:08低着头出来了 ,问的实在是太...