【力扣hot100】二叉树专题-北京尧图网络

文章目录104.二叉树的最大深度226. 翻转二叉树101.对称二叉树543. 二叉树的直径102.二叉树的层序遍历108. 将有序数组转换为二叉搜索树104.二叉树的最大深度104. 二叉树的最大深度递归/** * 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; * } * } */classSolution{publicintmaxDepth(TreeNoderoot){if(rootnull)return0;intleftmaxDepth(root.left);intrightmaxDepth(root.right);returnMath.max(left,right)1;}}226. 翻转二叉树226. 翻转二叉树先递归到底再交换/** * 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; * } * } */classSolution{publicTreeNodeinvertTree(TreeNoderoot){if(rootnull)returnnull;invertTree(root.left);invertTree(root.right);TreeNodetemproot.left;root.leftroot.right;root.righttemp;returnroot;}}101.对称二叉树101. 对称二叉树将整棵树的对称问题转化为判断“左子树”和“右子树”是否互为镜像。通过check函数每次递归都严格比较两个节点的值是否相等然后让左节点的“左孩子”与右节点的“右孩子”对比同时让左节点的“右孩子”与右节点的“左孩子”对比即交叉比较一路递归到底只要所有交叉对应的节点都匹配整棵树就是对称的/** * 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; * } * } */classSolution{publicbooleanisSymmetric(TreeNoderoot){returncheck(root.left,root.right);}publicbooleancheck(TreeNodeleft,TreeNoderight){//两边都为空对称if(leftnullrightnull)returntrue;//只有一边为空或者值不同不对称if(leftnull||rightnull||left.val!right.val)returnfalse;//继续向下交叉比较returncheck(left.left,right.right)check(left.right,right.left);}}543. 二叉树的直径543. 二叉树的直径遍历二叉树在计算最大深度的同时顺带把直径算出来在当前节点拐点的直径长度左子树的最大深度右子树的最大深度返回给父节点的是当前子树的最大深度 max(左子树的最大深度右子树的最大深度)1/** * 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; * } * } */classSolution{privateintres0;publicintdiameterOfBinaryTree(TreeNoderoot){maxDepth(root);returnres;}publicintmaxDepth(TreeNoderoot){if(rootnull)return0;intleftmaxDepth(root.left);intrightmaxDepth(root.right);resMath.max(res,leftright);returnMath.max(left,right)1;}}102.二叉树的层序遍历102. 二叉树的层序遍历BFScur数组存当前正在遍历的节点nxt数组存被遍历节点的左右子节点vals数组存部分答案遍历cur把左右子节点记录到nxt中同时把节点值记录到数组vals中遍历结束后把vals加到答案里遍历结束把cur替换成nxt开始下一轮循环cur不为空就证明还没遍历完/** * 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; * } * } */classSolution{publicListListIntegerlevelOrder(TreeNoderoot){if(rootnull)returnList.of();ListListIntegeransnewArrayList();ListTreeNodecurList.of(root);while(!cur.isEmpty()){ListTreeNodenxtnewArrayList();ListIntegervalsnewArrayList(cur.size());for(TreeNodenode:cur){vals.add(node.val);if(node.left!null)nxt.add(node.left);if(node.right!null)nxt.add(node.right);}curnxt;ans.add(vals);}returnans;}}优化一下把cur数组和nxt数组用一个队列替代/** * 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; * } * } */classSolution{publicListListIntegerlevelOrder(TreeNoderoot){if(rootnull)returnList.of();ListListIntegeransnewArrayList();QueueTreeNodeqnewArrayDeque();q.add(root);while(!q.isEmpty()){intnq.size();ListIntegervalsnewArrayList(n);while(n0){TreeNodenodeq.poll();vals.add(node.val);if(node.left!null)q.add(node.left);if(node.right!null)q.add(node.right);n--;}ans.add(vals);}returnans;}}108. 将有序数组转换为二叉搜索树108. 将有序数组转换为二叉搜索树平衡二叉搜索树每个节点的左子树和右子树高度相差不超过1由于给定的数组是严格升序的要构建一棵高度平衡的二叉搜索树BST关键在于每次都选取当前区间的中间元素作为根节点这样能保证左右子树的节点数量尽可能相等随后以中间元素为界将数组一分为二递归地对左半区间构建左子树、对右半区间构建右子树直到区间越界left right时返回null作为递归出口最终自底向上拼接出一棵完美的平衡二叉搜索树。/** * 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; * } * } */classSolution{publicTreeNodesortedArrayToBST(int[]nums){returnbuild(nums,0,nums.length-1);}publicTreeNodebuild(int[]nums,intleft,intright){if(leftright)returnnull;intmid(leftright)/2;TreeNoderootnewTreeNode(nums[mid]);root.leftbuild(nums,left,mid-1);root.rightbuild(nums,mid1,right);returnroot;}}

【力扣hot100】二叉树专题

相关推荐

家用电梯方案为什么每家不一样？看懂宽深比例选型逻辑不踩坑

Wingman：Go语言AI Agent开发框架，告别胶水代码地狱

四大开源AI智能体框架横向评测：从OpenClaw到CrewAI的选型指南

更多资讯

pstack-claude：给Claude Code做进程诊断的轻量工具

Python读取Oracle数据乱码问题解决：用TaoToken统一Key排查cx_Oracle编码链路

存储器容量扩展实战：位扩展与字扩展原理、连线与调试

最新NDK下载与32/64位ABI配置实战指南

MQTT.fx连接A云平台报错Bad user name or password？一文搞定参数排查

嵌入式C++内存管理实战：从内存分区到内存池与排查技巧

今日更新

PHP htmlentities()函数用法讲解

AI Agent工程实战：从七要素到七个决策点的系统设计指南

AI入局芯片设计验证：验证收敛50倍加速的真相与应对

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？