hot100-二叉树

二叉树

二叉树递归

相当于这个的顺序来回调换

class Solution {private List<Integer> res = new ArrayList<>();public List<Integer> inorderTraversal(TreeNode root) {if(root == null)return res;inorderTraversal(root.left);res.add(root.val);inorderTraversal(root.right);return res;}
}

二叉树迭代

前序遍历

迭代法
public List<Integer> preOrderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();if (root == null) {return res;}Deque<TreeNode> stack = new LinkedList<TreeNode>();TreeNode node = root;while (!stack.isEmpty() || node != null) {while (node != null) {res.add(node.val);stack.push(node);node = node.left;}node = stack.pop();node = node.right;}return res;
}

中序遍历

迭代法
public List<Integer> preOrderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();if (root == null) {return res;}Deque<TreeNode> stack = new LinkedList<TreeNode>();TreeNode node = root;while (!stack.isEmpty() || node != null) {while (node != null) {stack.push(node);node = node.left;}node = stack.pop();res.add(node.val);node = node.right;}return res;
}
染色法

缺点是要写一个pair的类，优点是只需要更改顺序就可以使三个顺序都能写

class Pair<K, V> {private K key;private V value;public Pair(K key, V value) {this.key = key;this.value = value;}public K getKey() {return key;}public V getValue() {return value;}
}class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new LinkedList<>();Deque<Pair<Integer, TreeNode>> stack = new ArrayDeque<>();stack.push(new Pair<>(0,root));while(!stack.isEmpty()){Pair<Integer,TreeNode> newPair = stack.pop();int color = newPair.getKey();TreeNode node = newPair.getValue();if(node == null)continue;if(color == 0){stack.push(new Pair<>(0,node.right));stack.push(new Pair<>(1,node));stack.push(new Pair<>(0,node.left));}else{res.add(node.val);}}return res;}
}
Morris法

①第一个循环：是否为空

②判断左子树是否为空，是则记录+进入右子树，不是则进入左子树

③如果最右的最右为空，则链接，进入左子树。如果最右的最右为root，则断联，记录，进入右子树。

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new LinkedList<>();while(root !=null){if(root.left == null){res.add(root.val);root = root.right;}else{//有左子树的情况TreeNode pre = root.left;while(pre.right != null && pre.right != root){pre = pre.right;}if(pre.right == null){pre.right = root;root = root.left;}else{pre.right = null;//断开res.add(root.val);root = root.right;}}}return res;}
}

后序遍历

反转法

其实就是将递归暗处的栈变成明面

public class PostorderTraversal {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null) return result;Stack<TreeNode> stack = new Stack<>();Stack<Integer> output = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();output.push(node.val);if (node.left != null) stack.push(node.left);if (node.right != null) stack.push(node.right);}while (!output.isEmpty()) {result.add(output.pop());}return result;}
访问标记法（染色法）

（使用额外的标记来指示节点是否已经访问）

public class PostorderTraversal {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null) return result;Stack<TreeNode> stack = new Stack<>();TreeNode prev = null;while (!stack.isEmpty() || root != null) {while (root != null) {stack.push(root);root = root.left;}root = stack.peek();if (root.right == null || root.right == prev) {result.add(root.val);stack.pop();prev = root;root = null; // We have finished this node} else {root = root.right; // Move to the right child}}return result;}
Morris法（线性时间，常数空间）

Morris 遍历法通过在遍历过程中使用指针而避免了使用栈或递归，从而节省空间。

public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null) return result;TreeNode dummy = new TreeNode(0);dummy.left = root;TreeNode curr = dummy;while (curr != null) {if (curr.left == null) {curr = curr.right;} else {TreeNode prev = curr.left;while (prev.right != null && prev.right != curr) {prev = prev.right;}if (prev.right == null) {prev.right = curr;curr = curr.left;} else {reverse(curr.left, prev);TreeNode temp = prev;while (temp != null) {result.add(temp.val);temp = temp.right;}reverse(prev, curr.left);prev.right = null;curr = curr.right;}}}return result;}private void reverse(TreeNode from, TreeNode to) {if (from == to) return;TreeNode x = from, y = from.right;while (x != to) {x.right = y.right;y.right = x;x = y;y = y.right;}}

104. 二叉树的最大深度

解法一、递归 

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

226. 翻转二叉树

解法一、递归

class Solution {public TreeNode invertTree(TreeNode root) {if(root == null)return root;invertTree(root.left);invertTree(root.right);TreeNode tmp = root.left;root.left = root.right;root.right = tmp;return root;}
}

101. 对称二叉树

解法一、递归

class Solution {public boolean isSymmetric(TreeNode root) {return isS(root.left,root.right);}private boolean isS(TreeNode left,TreeNode right){if(left == null || right == null)return left == right;return left.val == right.val && isS(left.left,right.right)&&isS(left.right,right.left);}
}

解法二、迭代 

因为List情况下不能add null，所以改换成Queue。不过不改也可以，只需要在null的情况下构建新节点，总之就是改换边界条件

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

543. 二叉树的直径

解法一、递归

class Solution {private int res = 0;public int diameterOfBinaryTree(TreeNode root) {dfs(root);return res;}private  int dfs(TreeNode root){if(root == null)return -1;int l = dfs(root.left)+1;int r = dfs(root.right)+1;res = Math.max(res,l+r);return Math.max(l,r);}
}

 
102. 二叉树的层序遍历

解法一 层序遍历

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {Queue<TreeNode> q = new LinkedList<>();List<List<Integer>> res = new LinkedList<>();q.offer(root);while(!q.isEmpty()){Queue<TreeNode> p = q;q = new LinkedList<>();List<Integer> tmp = new LinkedList<>();while(!p.isEmpty()){TreeNode node = p.poll();if(node == null)continue;q.add(node.left);q.add(node.right);tmp.add(node.val);}if(!tmp.isEmpty())res.add(tmp);}return res;}
}

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

解法一、递归

class Solution {public TreeNode sortedArrayToBST(int[] nums) {int n = nums.length,mid = n/2;return create(nums,0,n);}private TreeNode create(int[] nums,int x,int y){if(x==y)return null;int mid = x + (y-x)/2;TreeNode node = new TreeNode(nums[mid]);node.left = create(nums,x,mid);node.right = create(nums,mid+1,y);return node;}
}

98. 验证二叉搜索树

解法一、递归

class Solution {public boolean isValidBST(TreeNode root) {if(root == null)return true;return BST(root.left,Long.MIN_VALUE,root.val) && BST(root.right,root.val,Long.MAX_VALUE);}public boolean BST(TreeNode root,long x,long y) {if(root == null)return true;if(root.val <= x || root.val >= y )return false;return BST(root.left,x,root.val) && BST(root.right,root.val,y);}
}

 解法二、中序递增

中序出来的数组一定是递增的，同时，递增数组中序构建也一定是BST

class Solution {public boolean isValidBST(TreeNode root) {List<Integer> tmp = new LinkedList<>();while(root != null){if(root.left == null){tmp.add(root.val);root = root.right;}else{TreeNode node = root.left;while(node.right != null && node.right != root){node = node.right;}if(node.right == null){node.right = root;root = root.left;}else{node.right = null;tmp.add(root.val);root = root.right;}}}int n = tmp.size(),num = tmp.get(0);for(int i = 1;i < n;i++){if(tmp.get(i) <= num)return false;num = tmp.get(i);}return true;}
}

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

解法一、中序递增

98的变式。在while里判断一下tmp.size()和k的关系剪枝，可以效率提升一半多。

class Solution {public int kthSmallest(TreeNode root, int k) {List<Integer> tmp = new LinkedList<>();while(root != null){if(root.left == null){tmp.add(root.val);root = root.right;}else{TreeNode node = new TreeNode();while(node.right != null && node.right != root){node = node.right;}if(node.right == null){node.right = root;}else{node.right = null;tmp.add(root.val);root = root.right;}}}return tmp.get(k);}
}

 解法二、dfs

第一个if是边界，第二个if是剪枝，第三个是答案赋值判断

class Solution {private int k,res= 0;public int kthSmallest(TreeNode root, int k) {this.k = k;dfs(root);return res;}private void dfs(TreeNode root){if(root==null)return;dfs(root.left);if(k==0)return;if(--k==0)res = root.val;dfs(root.right);}
}

199. 二叉树的右视图

解法一、递归

class Solution {public List<Integer> rightSideView(TreeNode root) {Deque<TreeNode> a = new LinkedList<>();a.add(root);List<Integer> res = new LinkedList<>();if(root == null)return res;while(!a.isEmpty()){Deque<TreeNode> q = a;a = new LinkedList<>();res.add(q.getLast().val);while(!q.isEmpty()){TreeNode node = q.pollLast();if(node.right != null)a.addFirst(node.right);if(node.left != null)a.addFirst(node.left);}}return res;}
}


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


 

解法一、递归

靠前序确定节点 靠中序确定左右树 从顶至下递归进行

两个改进：①搜索改进，甚至使用哈希表O（1）。②更改函数传入，l和r，避免复制数组的开销

class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {int n = preorder.length;if(n==0)return null;int index = findNum(inorder,preorder[0]);int [] l = Arrays.copyOfRange(inorder,0,index);int [] r = Arrays.copyOfRange(inorder,index+1,n);int [] pre1 = Arrays.copyOfRange(preorder,1,1+index);int [] pre2 = Arrays.copyOfRange(preorder,1+index,n);TreeNode left = buildTree(pre1,l);TreeNode right = buildTree(pre2,r);return new TreeNode(preorder[0],left,right);}public int findNum(int[] nums,int num){int n = nums.length;for(int i = 0;i < n;i++){if(nums[i] == num)return i;}return -1;}
}

437. 路径总和 III

解法一、 递归 哈希

务必恢复现场

class Solution {private int ans;public int pathSum(TreeNode root, int targetSum) {Map<Long,Integer>cnt = new HashMap<>();cnt.put(0L,1);dfs(root,0,targetSum,cnt);return ans;}private void dfs(TreeNode root,long s,int targetSum,Map<Long,Integer> cnt){if(root == null)return;s+= root.val;ans += cnt.getOrDefault(s - targetSum, 0);cnt.merge(s,1,Integer::sum);dfs(root.left,s,targetSum,cnt);dfs(root.right,s,targetSum,cnt);cnt.merge(s,-1,Integer::sum);}
}

236. 二叉树的最近公共祖先

解法一、递归找路径，判断两条路径共同开头

你根本无法理解这个到底有多慢jpg

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {List<TreeNode> l = new LinkedList<>();List<TreeNode> r = new LinkedList<>();dfs(root,p,l);dfs(root,q,r);int n = l.size(),m = r.size(),x = 0,y = 0;while(x < n && y < m && l.get(x) == r.get(y)){x++;y++;}TreeNode res;if(x>=n)res = l.get(n-1);else if(y>=m)res = r.get(m-1);else res = l.get(x-1);return res;}public boolean dfs(TreeNode root,TreeNode p,List<TreeNode> list){if(root == null)return false;list.add(root);if(root == p){return true;}//都是错的才removeif(dfs(root.left,p,list) || dfs(root.right,p,list))return true;list.remove(list.size()-1);return false;}
}

 解法二、递归

进行了一个很大的剪枝。都=null即都没查到，两个都非null即当前节点就公共，p在q下面则返回q即可。

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;return left != null ? left : right;}}

124. 二叉树中的最大路径和​​​​​​​

解法一、递归

class Solution {private int res = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {dfs(root);return res;}private int dfs(TreeNode root){if(root == null)return 0;int left = dfs(root.left);int right = dfs(root.right);res = Math.max(left+right+root.val,res);return Math.max(0,Math.max(left+root.val,right+root.val));} 
}

 

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

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

相关文章

【JavaWeb13】了解ES6的核心特性，对于提高JavaScript编程效率有哪些潜在影响？

【JavaWeb13】了解ES6的核心特性，对于提高JavaScript编程效率有哪些潜在影响？

文章目录 &#x1f30d;一. ES6 新特性❄️1. ES6 基本介绍❄️2. 基本使用2.1 let 声明变量2.2 const 声明常量/只读变量2.3 解构赋值2.4 模板字符串2.5 对象拓展运算符2.6 箭头函数 &#x1f30d;二. Promise❄️1. 基本使用❄️2. 如何解决回调地狱问题2.1回调地狱问题2.2 使…
阅读更多...
ROS的action通信——实现阶乘运算（三）

ROS的action通信——实现阶乘运算（三）

在ROS中除了常见的话题(topic&#xff09;通信、服务(server)通信等方式&#xff0c;还有action通信这一方式&#xff0c;由于可以实时反馈任务完成情况&#xff0c;该通信方式被广泛运用于机器人导航等任务中。本文将通过三个小节的分享&#xff0c;实现基于action通信的阶乘运…
阅读更多...
centos系统MBR格式转换成gpt格式 （华为云）

centos系统MBR格式转换成gpt格式 （华为云）

在华为云上的centos7.9系统MBR格式转换成GPT格式的步骤 华为云上关于转换的步骤 这个链接里面 gdisk -g /dev/vda 是不对的&#xff0c;-g参数是新创建一个分区&#xff0c;慎用 自己步骤如下&#xff1a;&#xff08;已经试验过&#xff09; 1、gdisk /dev/sda (这里是盘 不…
阅读更多...
【Microsoft PowerPoint for Mac】2分钟配置-MAC一键删除PPT中的所有备注

【Microsoft PowerPoint for Mac】2分钟配置-MAC一键删除PPT中的所有备注

MAC一键删除PPT中的所有备注 1.搜索自动操作2.点击快速操作3.搜索并运行AppleScript4.输入代码&#xff0c;并选择只应用于Microsoft PowerPoint for Mac【右上角】5. CRTLS保存为“清除当前文稿中的所有备注”&#xff0c;PPT中应用。 MAC没自带&#xff0c;需要自己配置 1.搜…
阅读更多...
uni-app 开发 App 、 H5 横屏签名（基于lime-signature）

uni-app 开发 App 、 H5 横屏签名（基于lime-signature）

所用插件&#xff1a;lime-signature 使用到 CSS 特性 绝对定位transform 旋转transform-origin transform 原点 复习一下定位元素&#xff08;相对定位、绝对定位、粘性定位&#xff09; 代码# <template><view class"signature-page"><view clas…
阅读更多...
【Linux探索学习】第三十一弹——线程互斥与同步（下）：深入理解确保线程安全的机制

【Linux探索学习】第三十一弹——线程互斥与同步（下）：深入理解确保线程安全的机制

线程互斥与同步&#xff08;上&#xff09;&#xff1a;【Linux探索学习】第三十弹——线程互斥与同步&#xff08;上&#xff09;&#xff1a;深入理解线程保证安全的机制-CSDN博客 Linux探索学习&#xff1a; https://blog.csdn.net/2301_80220607/category_12805278.html?…
阅读更多...
《Effective Objective-C》阅读笔记（中）

《Effective Objective-C》阅读笔记（中）

目录 接口与API设计 用前缀避免命名空间冲突 提供“全能初始化方法” 实现description方法 尽量使用不可变对象 使用清晰而协调的命名方式 方法命名 ​编辑类与协议命名 为私有方法名加前缀 理解OC错误模型 理解NSCopying协议 协议与分类 通过委托与数据源协议进行…
阅读更多...
python-leetcode-每日温度

python-leetcode-每日温度

739. 每日温度 - 力扣&#xff08;LeetCode&#xff09; class Solution:def dailyTemperatures(self, temperatures: List[int]) -> List[int]:n len(temperatures)answer [0] * nstack [] # 存储索引for i, temp in enumerate(temperatures):while stack and temperat…
阅读更多...
山东大学软件学院nosql实验三

山东大学软件学院nosql实验三

实验题目&#xff1a; 用Java做简单查询(2学时) 实验内容 用API方式&#xff0c;做简单查询。 实验要求 在以下要求中选择至少2个&#xff0c;使用Java语言实现数据查询&#xff0c;最终把数据输出到前端界面。 &#xff08;1&#xff09;找出年龄小于20岁的所有学生 &…
阅读更多...
【Linux】初探信号的奥秘

【Linux】初探信号的奥秘

目录 一、引入信号&#xff1a; 1、什么是信号&#xff1a; 二、前后台进程&#xff1a; 三、信号的处理方式&#xff1a; 四、键盘数据与信号&#xff1a; 前言&#xff1a; 在Linux系统编程中&#xff0c;信号&#xff08;Signal&#xff09;是一种至关重要的进程间通信…
阅读更多...
Bugku CTF CRYPTO

Bugku CTF CRYPTO

Bugku CTF CRYPTO 文章目录 Bugku CTF CRYPTO聪明的小羊ok[-<>]散乱的密文.!? 聪明的小羊 描 述: 一只小羊翻过了2个栅栏 fa{fe13f590lg6d46d0d0} 分 析&#xff1a;栅栏密码&#xff0c;分2栏&#xff0c;一个栏里有11个 ①手动解密 f a { f e 1 3 f 5 9 0 l g 6 d 4 …
阅读更多...
数据库的基本操作

数据库的基本操作

目录 一、查看所有的数据库&#xff1a; 二、创建数据库&#xff1a; if not exists : 字符编码集&#xff1a; 排序规则&#xff1a; 三、查看创建的库&#xff1a; 四、修改数据库&#xff1a; 五、删除数据库&#xff1a; if exists&#xff1a; 前言&#xff1a; 在…
阅读更多...
IDEA集成DeepSeek，通过离线安装解决无法安装Proxy AI插件问题

IDEA集成DeepSeek，通过离线安装解决无法安装Proxy AI插件问题

文章目录 引言一、安装Proxy AI1.1 在线安装Proxy AI1.2 离线安装Proxy AI 二、Proxy AI中配置DeepSeek2.1 配置本地部署的DeepSeek&#xff08;Ollama方式&#xff09;2.2 通过第三方服务商提供的API进行配置 三、效果测试 引言 许多开发者尝试通过安装Proxy AI等插件将AI能力…
阅读更多...
Java+SpringBoot+Vue+数据可视化的音乐推荐与可视化平台（程序+论文+讲解+安装+调试+售后）

Java+SpringBoot+Vue+数据可视化的音乐推荐与可视化平台（程序+论文+讲解+安装+调试+售后）

感兴趣的可以先收藏起来&#xff0c;还有大家在毕设选题&#xff0c;项目以及论文编写等相关问题都可以给我留言咨询&#xff0c;我会一一回复&#xff0c;希望帮助更多的人。 系统介绍 在互联网技术以日新月异之势迅猛发展的浪潮下&#xff0c;5G 通信技术的普及、云计算能力…
阅读更多...
【时时三省】(C语言基础)常量和变量

【时时三省】(C语言基础)常量和变量

山不在高&#xff0c;有仙则名。水不在深&#xff0c;有龙则灵。 ----CSDN 时时三省 在计算机高级语言中&#xff0c;数据有两种表现形式&#xff1a;常量和变量。 常量 在程序运行过程中&#xff0c;其值不能被改变的量称为常量。数值常量就是数学中的常数。 常用的常量有以…
阅读更多...
zabbix故障案例 WEB页面Database error Connection refused

zabbix故障案例 WEB页面Database error Connection refused

目录 1.思路 2.问题解决 3.其他数据库问题思路 1.思路 当我们遇到 Database error Connection refused的问题的时候一般想到的都是数据库的问题 那我们这时候就顺着这条线索排查 2.问题解决 我们首先先进入数据库 mysql -uzabbix -p123 发现了如下报错 应该是数…
阅读更多...
MaxKB+Ollama+DeepSeek1.5B部署知识库

MaxKB+Ollama+DeepSeek1.5B部署知识库

环境信息 练习测试用&#xff0c;所以资源很低&#xff0c;8G显卡。大模型部署在Windows台式机上&#xff0c;MaxKB部署在CentOS虚拟机上。 台式机&#xff1a; 硬件&#xff1a;i7 13900 NV GeForce RTX 3060 Ti 8G显存 32G内存 软件&#xff1a;Windows 11操作系统&…
阅读更多...
猿大师播放器：智慧交通Web网页低延迟播放监控RTSP H.265视频解决方案

猿大师播放器：智慧交通Web网页低延迟播放监控RTSP H.265视频解决方案

在智慧城市建设加速推进的今天&#xff0c;智慧交通作为城市"神经系统"正面临前所未有的发展机遇。据统计&#xff0c;2023年全国交通视频监控设备保有量已突破4500万台&#xff0c;日均产生的视频数据量超50PB。但在这些庞大数字背后&#xff0c;行业却普遍面临着&q…
阅读更多...
Web3.py 入门笔记

Web3.py 入门笔记

Web3.py 学习笔记 &#x1f4da; 1. Web3.py 简介 &#x1f31f; Web3.py 是一个 Python 库&#xff0c;用于与以太坊区块链进行交互。它就像是连接 Python 程序和以太坊网络的桥梁。 官方文档 1.1 主要功能 查询区块链数据&#xff08;余额、交易等&#xff09;发送交易与…
阅读更多...
如何选择工控产线安全软件？

如何选择工控产线安全软件？

在当今数字化时代&#xff0c;信息安全的重要性不言而喻。随着工业控制系统&#xff08;ICS&#xff09;的广泛应用&#xff0c;主机的安全加固成为了保障企业生产运营稳定的关键环节。MCK-T主机加固系统软件&#xff0c;凭借其卓越的性能和全面的安全防护功能&#xff0c;成为…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023