Letcode-Top 100二叉树专题

94. 二叉树的中序遍历

在这里插入图片描述
方法一：递归法

/*** 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 List<Integer> inorderTraversal(TreeNode root) {List<Integer> arraylist=new ArrayList<>();if(root==null){return arraylist;}Stack<TreeNode> stack=new Stack<TreeNode>();TreeNode current=root;while(current!=null||!stack.isEmpty()){while(current!=null){stack.push(current);current=current.left;}current=stack.pop();arraylist.add(current.val);current=current.right;}return arraylist;}
}

方法二：迭代法

/*** 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 List<Integer> inorderTraversal(TreeNode root) {// 中序遍历List<Integer> res = new ArrayList<Integer>();inorderTraversal(root, res);return res;}public void inorderTraversal(TreeNode node, List<Integer> res) {if (node == null) {return;}inorderTraversal(node.left, res);res.add(node.val);inorderTraversal(node.right, res);}}

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;*     }* }*/
class Solution {public int maxDepth(TreeNode root) {if(root==null){return 0;}else {int leftLength = maxDepth(root.left)+1;int rightLength = maxDepth(root.right)+1;return Math.max(leftLength,rightLength);}}
}

方法二：层序遍历

class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;}int ans = 0;int size = 0;LinkedList<TreeNode> queue = new LinkedList<TreeNode>();queue.add(root);while (!queue.isEmpty()) {size = queue.size();while (size > 0) {root = queue.poll();if (root.left != null) {queue.offer(root.left);}if (root.right != null) {queue.offer(root.right);}size--;}ans++;}return ans;}
}

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;*     }* }*/
class Solution {public int maxDepth(TreeNode root) {if(root==null){return 0;}else {int leftLength = maxDepth(root.left)+1;int rightLength = maxDepth(root.right)+1;return Math.max(leftLength,rightLength);}}
}

方法二：迭代

class Solution {public TreeNode invertTree(TreeNode root) {if (root == null) {return null;}TreeNode node = root;Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.add(node);int size = 0;while (!queue.isEmpty()) {size = queue.size();while (size > 0) {TreeNode temp = queue.poll();TreeNode left = temp.left;if (left != null) {queue.offer(left);}TreeNode right = temp.right;if (right != null) {queue.offer(right);}temp.left = right;temp.right = left;size--;}}return root;}
}

101. 对称二叉树

在这里插入图片描述
方法一：递归

/*** 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 boolean isSymmetric(TreeNode root) {if (root == null) {return true;}return isSymmetric(root.left,root.right);}public boolean isSymmetric(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 isSymmetric(left.left,right.right)&& isSymmetric(left.right,right.left);}}

方法二：迭代

class Solution {public boolean isSymmetric(TreeNode root) {if (root == null) {return true;}return isSymmetric(root.left, root.right);}public boolean isSymmetric(TreeNode left, TreeNode right) {Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(left);queue.offer(right);while (!queue.isEmpty()) {left = queue.poll();right = queue.poll();if (left == null && right == null) {continue;}if (left == null || right == null || left.val != right.val) {return false;}queue.offer(left.left);queue.offer(right.right);queue.offer(left.right);queue.offer(right.left);}return true;}}

543. 二叉树的直径

在这里插入图片描述
方法一：递归

class Solution {int ans = 0;public int diameterOfBinaryTree(TreeNode root) {diameterOfBinaryTreePLus(root);return ans;}public int diameterOfBinaryTreePLus(TreeNode root) {if(root==null){return 0;}int left =  diameterOfBinaryTreePLus(root.left);int right = diameterOfBinaryTreePLus(root.right);ans = Math.max(ans,left+right);return Math.max(left+1,right+1);}
}

102. 二叉树的层序遍历

在这里插入图片描述

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<List<Integer>>();if (root == null) {return result;}Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);int size = 0;while (!queue.isEmpty()) {size = queue.size();List<Integer> list = new ArrayList<Integer>();while (size > 0) {TreeNode node = queue.poll();list.add(node.val);if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}size--;if (size == 0) {result.add(list);}}}return result;}
}

108. 将有序数组转换为二叉搜索树

在这里插入图片描述

class Solution {public TreeNode sortedArrayToBST(int[] nums) {return sortedArrayToBST(nums,0,nums.length-1);}public TreeNode sortedArrayToBST(int[] nums,int left,int right){if(left>right){return null;}int mid = (left+right)/2;TreeNode root = new TreeNode(nums[mid]);root.left =  sortedArrayToBST(nums,left,mid-1);root.right = sortedArrayToBST(nums,mid+1,right);return root;}
}

98. 验证二叉搜索树

在这里插入图片描述
方法一：递归

初始错误写法

class Solution {public boolean isValidBST(TreeNode root) {if (root == null) {return true;}if (root.left != null) {if (root.left.val >= root.val) {return false;}}if (root.right != null) {if (root.right.val <= root.val) {return false;}}boolean left = isValidBST(root.left);boolean right = isValidBST(root.right);return left && right;}
}

在这里插入图片描述
正确写法

/*** Definition for a binary tree node.* public class TreeNode {* long val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(long val) { this.val = val; }* TreeNode(long val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public boolean isValidBST(TreeNode root) {if (root == null) {return true;}return isValidBSTPlus(root,Long.MIN_VALUE,Long.MAX_VALUE);}public boolean isValidBSTPlus(TreeNode root,long min,long max) {if (root == null) {return true;}if (root.left != null) {if (root.left.val >= root.val) {return false;}}if (root.right != null) {if (root.right.val <= root.val) {return false;}}if(root.val>=max || root.val<=min){return false;}boolean left = isValidBSTPlus(root.left,min,root.val);boolean right = isValidBSTPlus(root.right,root.val,max);return left && right;}
}

方法二：中序遍历

/*** 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 boolean isValidBST(TreeNode root) {long limit = Long.MIN_VALUE;Stack<TreeNode> stack = new Stack<TreeNode>();TreeNode currentNode = root;while (currentNode != null || !stack.isEmpty()) {while (currentNode != null) {stack.push(currentNode);currentNode = currentNode.left;}currentNode = stack.pop();if (currentNode.val <= limit) {return false;}limit = currentNode.val;currentNode = currentNode.right;}return true;}
}

230. 二叉搜索树中第K小的元素

在这里插入图片描述
方法一：排序

class Solution {List<Integer> list = new ArrayList<>();public int kthSmallest(TreeNode root, int k) {sort(root);return list.get(k-1);}void sort(TreeNode root){if(root==null){return;}sort(root.left);list.add(root.val);sort(root.right);}
}

方法二：迭代

/*** 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 int kthSmallest(TreeNode root, int k) {TreeNode curNode = root;Stack<TreeNode> stack = new Stack<TreeNode>();while (!stack.isEmpty()||curNode!=null) {while (curNode != null) {stack.push(curNode);curNode = curNode.left;}curNode = stack.pop();k--;if (k == 0) {return curNode.val;}curNode = curNode.right;}return curNode.val;}
}

199. 二叉树的右视图

在这里插入图片描述
方法一：层序遍历

/*** 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 List<Integer> rightSideView(TreeNode root) {List<Integer> result = new ArrayList<Integer>();if (root == null) {return result;}TreeNode curNode = root;// 层序遍历Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.add(curNode);int size = 0;while (!queue.isEmpty()) {size = queue.size();while (size > 0) {curNode = queue.poll();if (curNode.left != null) {queue.offer(curNode.left);}if (curNode.right != null) {queue.offer(curNode.right);}size--;if (size == 0) {result.add(curNode.val);}}}return result;}
}

方法二：深度遍历 （根 右 左）

/*** 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<Integer>();public List<Integer> rightSideView(TreeNode root) {sort(root, 0);return result;}public void sort(TreeNode root, Integer length) {if (root == null) {return;}if (length == result.size()) {result.add(root.val);}length++;sort(root.right, length);sort(root.left, length);}
}

105. 从前序与中序遍历序列构造二叉树

在这里插入图片描述
方法一：递归方法

class Solution {int[] preorder;HashMap<Integer,Integer> dic = new HashMap<>();public TreeNode buildTree(int[] preorder, int[] inorder) {this.preorder = preorder;for(int i=0;i<inorder.length;i++){dic.put(inorder[i],i);}return recur(0,0,inorder.length-1);}TreeNode recur(int root,int left,int right){if(left>right){return null;}TreeNode node = new TreeNode(preorder[root]);int i = dic.get(preorder[root]);node.left = recur(root+1,left,i-1);node.right = recur(root+i-left+1,i+1,right);return node;}}

方法二：迭代方法
暂时放弃

迭代方法

437. 路径总和 III

在这里插入图片描述
方法一：常规迭代

/*** 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 int pathSum(TreeNode root, int targetSum) {if(root==null){return 0;}int ret = rootSum(root,targetSum);ret += pathSum(root.left,targetSum);ret += pathSum(root.right,targetSum);return ret;}public int rootSum(TreeNode root, long targetSum) {int ret = 0;if (root == null) {return 0;}int val = root.val;if (val == targetSum) {ret++;}ret += rootSum(root.left, targetSum - val);ret += rootSum(root.right, targetSum - val);return ret;}
}

方法二：前缀法

前缀和Letcode链接


/*** 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 {Map<Long, Integer> prefixMap;int target;public int pathSum(TreeNode root, int targetSum) {prefixMap = new HashMap<>();target = targetSum;prefixMap.put(0l, 1);return recur(root, 0l);}private int recur(TreeNode node, Long curSum) {if (node == null) {return 0;}int res = 0;curSum += node.val;res += prefixMap.getOrDefault(curSum - target, 0);prefixMap.put(curSum, prefixMap.getOrDefault(curSum, 0) + 1);int left = recur(node.left, curSum);int right = recur(node.right, curSum);res = res + left + right;prefixMap.put(curSum, prefixMap.get(curSum) - 1);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){return root;}if(left!=null){return left;}if(right!=null){return right;}return null;}
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/346019.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

【python】在【机器学习】与【数据挖掘】中的应用：从基础到【AI大模型】

【python】在【机器学习】与【数据挖掘】中的应用：从基础到【AI大模型】

目录 &#x1f497;一、Python在数据挖掘中的应用&#x1f495; &#x1f496;1.1 数据预处理&#x1f49e; &#x1f496;1.2 特征工程&#x1f495; &#x1f497;二、Python在机器学习中的应用&#x1f495; &#x1f496;2.1 监督学习&#x1f49e; &#x1f496;2.2…
阅读更多...
第1章Hello world 3/5：Cargo.lock：确保构建稳定可靠：运行第一个程序

第1章Hello world 3/5：Cargo.lock：确保构建稳定可靠：运行第一个程序

讲动人的故事，写懂人的代码 1.6 Cargo.lock：确保构建稳定可靠 “看！”席双嘉一边指着屏幕一边说，“终端窗口提示符的颜色，从绿变黄了。这就意味着代码在上次提交后有点变化。” 赵可菲：“但是我们只是运行了程序，代码应该没动呀。” 席双嘉敲了下git status -uall，这…
阅读更多...
计网总结☞网络层

计网总结☞网络层

.................................................. 思维导图 ........................................................... 【Wan口和Lan口】 WAN口&#xff08;Wide Area Network port&#xff09;&#xff1a; 1)用于连接外部网络&#xff0c;如互联…
阅读更多...
SpringBoot学习笔记

SpringBoot学习笔记

总体思路&#xff1a;先写dao,再写service 1.https://start.spring.io 生成对应的模板 2.写TestCotroller类&#xff0c;类上写RestCotroller注解 3.TestCotroller类里写方法&#xff0c;方法上写GetMapping("/方法名")注解 4.不一定要写GetMapping,具体看做什么操…
阅读更多...
MySQL从入门到高级 --- 15.优化 16.pymysql

MySQL从入门到高级 --- 15.优化 16.pymysql

文章目录 第十五章 && 第十六章&#xff1a;15.优化15.1 查询SQL执行效率15.2 定位低效率执行SQL15.3 explain分析执行计划 - 基本使用15.4 explain分析执行计划 - id15.5 explain分析执行计划 - select_type15.6 explain分析执行计划 - type15.7 explain分析执行计划 …
阅读更多...
MySQL高性能（MySQL锁）

MySQL高性能（MySQL锁）

MySQL性能系列 MySQL锁 前言1. 死锁机制2. 思维导图与锁划分介绍3. 粒度划分锁3.1. 全局锁3.2. 页级锁&#xff08;Page-level locking&#xff09;3.3. 表级锁&#xff08;Tables-level lock&#xff09;○ 共享锁&#xff08;表级&#xff09;○ 排他锁&#xff08;表级&…
阅读更多...
字节面试：CPU100% 如何处理？

字节面试：CPU100% 如何处理？

尼恩说在前面 在40岁老架构师 尼恩的读者交流群(50)中&#xff0c;最近有小伙伴拿到了一线互联网企业如得物、阿里、滴滴、极兔、有赞、希音、百度、网易、美团的面试资格&#xff0c;遇到很多很重要的线上问题的场景题&#xff1a; 1.CPU100%&#xff0c;你是怎么处理的&…
阅读更多...
jvm学习笔记(二) ----- 垃圾回收

jvm学习笔记(二) ----- 垃圾回收

GC 一、判定对象是否是垃圾1.引用计数法2.可达性分析算法 二、垃圾回收算法1.标记清除2.标记整理3. 复制4. 分代垃圾回收1.尝试在伊甸园分配2.大对象直接晋升至老年代3.多次存活的对象4.老年代连续空间不足&#xff0c;触发 Full GC 链接: jvm学习笔记(一) ----- JAVA 内存 链接…
阅读更多...
C++程序设计：对数据文件的操作与文件流

C++程序设计：对数据文件的操作与文件流

姚老师小课堂开课啦&#xff01; 一、文件的分类&#xff1a; 1.ASCII码文件&#xff1a; ASCII文件使用方便&#xff0c;比较直观&#xff0c;便于阅读&#xff0c;便于对字符进行输入输出&#xff0c;但一般占用存储空间较多&#xff0c;而且需要花费转换时间&#xff08;二…
阅读更多...
④-2单细胞学习-cellchat单数据代码补充版（通讯网络）

④-2单细胞学习-cellchat单数据代码补充版（通讯网络）

目录 通讯网络系统分析 ①社会网络分析 1&#xff0c;计算每个细胞群的网络中心性指标 2&#xff0c;识别细胞的信号流模式 ②非负矩阵分解&#xff08;NMF&#xff09;识别细胞的通讯模式 1&#xff0c;信号输出细胞的模式识别 2&#xff0c;信号输入细胞的模式识别 信…
阅读更多...
激光点云配准算法——Cofinet / GeoTransforme / MAC

激光点云配准算法——Cofinet / GeoTransforme / MAC

激光点云配准算法——Cofinet / GeoTransformer / MAC GeoTransformer MAC是当前最SOTA的点云匹配算法&#xff0c;在之前我用总结过视觉特征匹配的相关算法 视觉SLAM总结——SuperPoint / SuperGlue 本篇博客对Cofinet、GeoTransformer、MAC三篇论文进行简单总结 1. Cofine…
阅读更多...
计算机网络 期末复习（谢希仁版本）第8章

计算机网络 期末复习（谢希仁版本）第8章

元文件就是一种非常小的文件&#xff0c;它描述或指明其他文件的一些重要信息。这里的元文件保存了有关这个音频/视频文件的信息。 10. 流式&#xff1a;TCP&#xff1b;流式实况&#xff1a;UDP。
阅读更多...
10秒钟docker 安装Acunetix

10秒钟docker 安装Acunetix

1、拉取镜像&#xff1a; 2、查看镜像&#xff1a; [rootdns-server ~]# docker images REPOSITORY TAG IMAGE ID CREATED SIZE quay.io/hiepnv/acunetix latest f8415551b8f4 2 months ago 1.98GB 3、运行镜像&#xff1a; …
阅读更多...
Redis 单线程问题 BigKey问题

Redis 单线程问题 BigKey问题

前言 简单的redis基础类型以及常用操作我们都也已经介绍过了 现在今天我们来谈谈redis对于单线程是需要怎么理解的 以及redis假设遇见大key我们需要怎么去查询和删除呢??? redis单线程 假设有个人现在问你一个问题:redis是单线程的还是多线程的 这个问题本身就不严谨 就像问…
阅读更多...
Python通过数据验证功能在Excel文件中创建下拉列表

Python通过数据验证功能在Excel文件中创建下拉列表

Excel表格的灵活性和功能性深受各行各业人士的喜爱。在Excel表格中&#xff0c;下拉列表功能是提升数据录入效率与准确性的一个重要利器&#xff0c;能够为用户提供预设的选择项&#xff0c;限制输入范围&#xff0c;避免手动输入错误&#xff0c;还能够简化数据录入过程&#…
阅读更多...
深度学习（三）

深度学习（三）

5.Functional API 搭建神经网络模型 5.1利用Functional API编写宽深神经网络模型进行手写数字识别 import numpy as npimport pandas as pdimport matplotlib.pyplot as pltfrom sklearn.datasets import load_irisfrom sklearn.model_selection import train_test_splitfrom…
阅读更多...
Nginx配置详细解释：(3)http模块及server模块,location模块

Nginx配置详细解释：(3)http模块及server模块,location模块

目录 环境概述&#xff1a; http模块中的全局模块 1. root配置主要是对主web页面的路径访问。 2.server虚拟主机 2.1基于IP&#xff1a; 2.2基于域名&#xff1a; 3.alias别名 4.location匹配 5.access模块&#xff1a; 6.验证模块 7.自定义错误页面 8.日志存放位置…
阅读更多...
Clearedge3d EdgeWise 5.8 强大的自动化建模软件

Clearedge3d EdgeWise 5.8 强大的自动化建模软件

EdgeWise是功能强大的建模软件&#xff0c;提供领先的建模功能和先进的技术&#xff0c;让您的整个过程更快更准确&#xff01;您可以获得使用自动特征提取和对象识别的 3D 建模&#xff0c;ClearEdge3D 自动建模和对象识别软件通过创建竣工文档和施工验证完成该过程。拓普康和…
阅读更多...
Python第二语言（七、Python模块）

Python第二语言（七、Python模块）

目录 1. 什么是模块 2. 基本语法 2.1 模块的导入方式 2.2 基本语法 import 模块名 2.3 基本语法 from 模块名 import 功能名 2.4 基本语法as 别名 3. 自定义模块 4. 调用自定义模块时&#xff0c;如何让其模块中的函数不被调用&#xff08;__name__&#xff09; 5. 调…
阅读更多...
【数据结构与算法】使用数组实现栈：原理、步骤与应用

【数据结构与算法】使用数组实现栈：原理、步骤与应用

&#x1f493; 博客主页&#xff1a;倔强的石头的CSDN主页 &#x1f4dd;Gitee主页&#xff1a;倔强的石头的gitee主页 ⏩ 文章专栏&#xff1a;《数据结构与算法》 期待您的关注 ​ 目录 一、引言 &#x1f384;栈&#xff08;Stack&#xff09;是什么&#xff1f; &#x1…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发