class037 二叉树高频题目-下-不含树型dp【算法】

2023-12-07 20:12
文章标签 算法 二叉树 dp 题目 高频 不含 树型 class037

本文主要是介绍class037 二叉树高频题目-下-不含树型dp【算法】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

class037 二叉树高频题目-下-不含树型dp【算法】

在这里插入图片描述
在这里插入图片描述

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

// 普通二叉树上寻找两个节点的最近公共祖先
// 测试链接 : https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

package class037;// 普通二叉树上寻找两个节点的最近公共祖先
// 测试链接 : https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
public class Code01_LowestCommonAncestor {// 不提交这个类public static class TreeNode {public int val;public TreeNode left;public TreeNode right;}// 提交如下的方法public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null || root == p || root == q) {// 遇到空，或者p，或者q，直接返回return root;}TreeNode l = lowestCommonAncestor(root.left, p, q);TreeNode r = lowestCommonAncestor(root.right, p, q);if (l != null && r != null) {// 左树也搜到，右树也搜到，返回rootreturn root;}if (l == null && r == null) {// 都没搜到返回空return null;}// l和r一个为空，一个不为空// 返回不空的那个return l != null ? l : r;}}

code2 235. 二叉搜索树的最近公共祖先

// 搜索二叉树上寻找两个节点的最近公共祖先
// 测试链接 : https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/

package class037;// 搜索二叉树上寻找两个节点的最近公共祖先
// 测试链接 : https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/
public class Code02_LowestCommonAncestorBinarySearch {// 不提交这个类public static class TreeNode {public int val;public TreeNode left;public TreeNode right;}// 提交如下的方法public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// root从上到下// 如果先遇到了p，说明p是答案// 如果先遇到了q，说明q是答案// 如果root在p~q的值之间，不用管p和q谁大谁小，只要root在中间，那么此时的root就是答案// 如果root在p~q的值的左侧，那么root往右移动// 如果root在p~q的值的右侧，那么root往左移动while (root.val != p.val && root.val != q.val) {if (Math.min(p.val, q.val) < root.val && root.val < Math.max(p.val, q.val)) {break;}root = root.val < Math.min(p.val, q.val) ? root.right : root.left;}return root;}}

code3 113. 路径总和 II

// 收集累加和等于aim的所有路径
// 测试链接 : https://leetcode.cn/problems/path-sum-ii/

package class037;import java.util.ArrayList;
import java.util.List;// 收集累加和等于aim的所有路径
// 测试链接 : https://leetcode.cn/problems/path-sum-ii/
public class Code03_PathSumII {// 不提交这个类public static class TreeNode {public int val;public TreeNode left;public TreeNode right;}// 提交如下的方法public static List<List<Integer>> pathSum(TreeNode root, int aim) {List<List<Integer>> ans = new ArrayList<>();if (root != null) {List<Integer> path = new ArrayList<>();f(root, aim, 0, path, ans);}return ans;}public static void f(TreeNode cur, int aim, int sum, List<Integer> path, List<List<Integer>> ans) {if (cur.left == null && cur.right == null) {// 叶节点if (cur.val + sum == aim) {path.add(cur.val);copy(path, ans);path.remove(path.size() - 1);}} else {// 不是叶节点path.add(cur.val);if (cur.left != null) {f(cur.left, aim, sum + cur.val, path, ans);}if (cur.right != null) {f(cur.right, aim, sum + cur.val, path, ans);}path.remove(path.size() - 1);}}public static void copy(List<Integer> path, List<List<Integer>> ans) {List<Integer> copy = new ArrayList<>();for (Integer num : path) {copy.add(num);}ans.add(copy);}}

code4 110. 平衡二叉树

// 验证平衡二叉树
// 测试链接 : https://leetcode.cn/problems/balanced-binary-tree/

package class037;// 验证平衡二叉树
// 测试链接 : https://leetcode.cn/problems/balanced-binary-tree/
public class Code04_BalancedBinaryTree {// 不提交这个类public static class TreeNode {public int val;public TreeNode left;public TreeNode right;}// 提交如下的方法public static boolean balance;public static boolean isBalanced(TreeNode root) {// balance是全局变量，所有调用过程共享// 所以每次判断开始时，设置为truebalance = true;height(root);return balance;}// 一旦发现不平衡，返回什么高度已经不重要了public static int height(TreeNode cur) {if (!balance || cur == null) {return 0;}int lh = height(cur.left);int rh = height(cur.right);if (Math.abs(lh - rh) > 1) {balance = false;}return Math.max(lh, rh) + 1;}}

code5 98. 验证二叉搜索树

// 验证搜索二叉树
// 测试链接 : https://leetcode.cn/problems/validate-binary-search-tree/

code1 中序遍历判断是否升序
code2 递归

package class037;// 验证搜索二叉树
// 测试链接 : https://leetcode.cn/problems/validate-binary-search-tree/
public class Code05_ValidateBinarySearchTree {// 不提交这个类public static class TreeNode {public int val;public TreeNode left;public TreeNode right;}// 提交以下的方法public static int MAXN = 10001;public static TreeNode[] stack = new TreeNode[MAXN];public static int r;// 提交时改名为isValidBSTpublic static boolean isValidBST1(TreeNode head) {if (head == null) {return true;}TreeNode pre = null;r = 0;while (r > 0 || head != null) {if (head != null) {stack[r++] = head;head = head.left;} else {head = stack[--r];if (pre != null && pre.val >= head.val) {return false;}pre = head;head = head.right;}}return true;}public static long min, max;// 提交时改名为isValidBSTpublic static boolean isValidBST2(TreeNode head) {if (head == null) {min = Long.MAX_VALUE;max = Long.MIN_VALUE;return true;}boolean lok = isValidBST2(head.left);long lmin = min;long lmax = max;boolean rok = isValidBST2(head.right);long rmin = min;long rmax = max;min = Math.min(Math.min(lmin, rmin), head.val);max = Math.max(Math.max(lmax, rmax), head.val);return lok && rok && lmax < head.val && head.val < rmin;}}

code6 669. 修剪二叉搜索树

// 修剪搜索二叉树
// 测试链接 : https://leetcode.cn/problems/trim-a-binary-search-tree/

package class037;// 修剪搜索二叉树
// 测试链接 : https://leetcode.cn/problems/trim-a-binary-search-tree/
public class Code06_TrimBinarySearchTree {// 不提交这个类public static class TreeNode {public int val;public TreeNode left;public TreeNode right;}// 提交以下的方法// [low, high]public static TreeNode trimBST(TreeNode cur, int low, int high) {if (cur == null) {return null;}if (cur.val < low) {return trimBST(cur.right, low, high);}if (cur.val > high) {return trimBST(cur.left, low, high);}// cur在范围中cur.left = trimBST(cur.left, low, high);cur.right = trimBST(cur.right, low, high);return cur;}}

code7 337. 打家劫舍 III

// 二叉树打家劫舍问题
// 测试链接 : https://leetcode.cn/problems/house-robber-iii/

package class037;// 二叉树打家劫舍问题
// 测试链接 : https://leetcode.cn/problems/house-robber-iii/
public class Code07_HouseRobberIII {// 不提交这个类public static class TreeNode {public int val;public TreeNode left;public TreeNode right;}// 提交如下的方法public static int rob(TreeNode root) {f(root);return Math.max(yes, no);}// 全局变量，完成了X子树的遍历，返回之后// yes变成，X子树在偷头节点的情况下，最大的收益public static int yes;// 全局变量，完成了X子树的遍历，返回之后// no变成，X子树在不偷头节点的情况下，最大的收益public static int no;public static void f(TreeNode root) {if (root == null) {yes = 0;no = 0;} else {int y = root.val;int n = 0;f(root.left);y += no;n += Math.max(yes, no);f(root.right);y += no;n += Math.max(yes, no);yes = y;no = n;}}}

这篇关于class037 二叉树高频题目-下-不含树型dp【算法】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/467214。

相关文章

openCV中KNN算法的实现

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库，它提供了各
阅读更多...
springboot+dubbo实现时间轮算法

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n
阅读更多...
SpringBoot实现MD5加盐算法的示例代码

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.
阅读更多...
SpringBoot启动报错的11个高频问题排查与解决终极指南

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突：NoSuchMethodError 的终极解法2. Bean注入失败：No qu
阅读更多...
Java时间轮调度算法的代码实现

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组（时间轮）和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时
阅读更多...
如何通过Golang的container/list实现LRU缓存算法

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣：146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.
阅读更多...
golang字符串匹配算法解读

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt（KMP）算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串（称为
阅读更多...
通俗易懂的Java常见限流算法具体实现

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》：本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1
阅读更多...
Python中的随机森林算法与实战

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例：使用随机森林预测鸢尾花品种4.1
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2