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) {
			// 左树也搜到，右树也搜到，返回root
			return 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是全局变量，所有调用过程共享
		// 所以每次判断开始时，设置为true
		balance = 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;

	// 提交时改名为isValidBST
	public 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;

	// 提交时改名为isValidBST
	public 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;
		}
	}

}

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

上个月暴涨34.6%后，SoundHound AI股票现在还能买入吗？

上个月暴涨34.6%后，SoundHound AI股票现在还能买入吗？

来源&#xff1a;猛兽财经 作者&#xff1a;猛兽财经 揭开SoundHound AI股价波动的原因 S&P Global Market Intelligence的数据显示&#xff0c;在摆脱了10月份的大幅下跌后&#xff0c;SoundHound AI的股价在11月份实现了34.6%的涨幅。 原因是该公司公布了稳健的第三季…
阅读更多...
三数组最小距离：2020年408算法题

三数组最小距离：2020年408算法题

算法思想 算法实现 #define INT_MAX 0x7fffffff //c语言int类型最大值 //计算绝对值 int abs(int a){if(a<0) return -a;else return a; } //判断a是否为3个数中最小值 bool isMin(int a,int b,int c){if(a<b&&a<c) return true;return false; }//主函数 in…
阅读更多...
Linux——web网站服务（一）

Linux——web网站服务（一）

一、安装httpd服务器Apache网站服务 1、准备工作 为了避免发送端口冲突&#xff0c;程序冲突等现象&#xff0c;卸载使用rpm方式安装的httpd #使用命令检查是否下载了httpd [rootserver ~]# rpm -qa httpd #如果有则使用 [rootserver ~]# rpm -e httpd --nodeps Apache的配置…
阅读更多...
欧拉回路欧拉路【详解】

欧拉回路欧拉路【详解】

1.引入 2.概念 3.解决方法 4.例题 5.回顾 1.引入 经典的七桥问题 哥尼斯堡是位于普累格河上的一座城市&#xff0c;它包含两个岛屿及连接它们的七座桥&#xff0c;如下图所示。 可否走过这样的七座桥&#xff0c;而且每桥只走过一次&#xff1f; 你怎样证明&#xff1f;…
阅读更多...
mysql数据库中int字段长度，即int(1)和int(10)的区别

mysql数据库中int字段长度，即int(1)和int(10)的区别

1.起因 为什么想起来看这个问题&#xff0c;是最近有同事问mysql的init类型的字段长度的问题&#xff0c;他问int(1)和int(10)是什么意思&#xff0c;是字段长度越大&#xff0c;能存储的数字越大么&#xff1f;咋一问&#xff0c;还有点懵&#xff0c;从惯性思维来看&#xf…
阅读更多...
合并两个有序数组（leetcode_刷题1）

合并两个有序数组（leetcode_刷题1）

目录 题目&#xff1a;合并两个有序数组 题目分析方向1&#xff1a; 题目分析方向2&#xff1a; 题目&#xff1a;合并两个有序数组 题目要求&#xff1a; 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2&#xff0c;另有两个整数 m 和 n &#xff0c;分别表示 nums…
阅读更多...
在python中安装库，会有conda安装，也会有pip安装，conda与pip的区别是什么？

在python中安装库，会有conda安装，也会有pip安装，conda与pip的区别是什么？

文章目录 一、Conda是什么&#xff1f;二、pip是什么&#xff1f;三、pip与conda的区别&#xff1a;总结 一、Conda是什么&#xff1f; Conda是一个开源的包管理系统&#xff0c;它是Anaconda公司为Python和其他编程语言开发的。它主要用于数据科学和机器学习领域&#xff0c;…
阅读更多...
SpringIOC之@Configuration

SpringIOC之@Configuration

博主介绍&#xff1a;✌全网粉丝5W&#xff0c;全栈开发工程师&#xff0c;从事多年软件开发&#xff0c;在大厂呆过。持有软件中级、六级等证书。可提供微服务项目搭建与毕业项目实战&#xff0c;博主也曾写过优秀论文&#xff0c;查重率极低&#xff0c;在这方面有丰富的经验…
阅读更多...
字符串指令集

字符串指令集

字符串指令的格式 例子1就成功发送了指令 例子2就是发送的字符串有误 查询当前位置就会在附加信息中返回当前座位的坐标 第一个指令的参数就是闪灯的两个参数 如第一个示例就是10ms On Time 第二个就是Off Time 使用标准库来接收字符串命令 字符串指令的接收 因为一个指令就是…
阅读更多...
麒麟系统进入救援模式或者是crtl D界面排查方法

麒麟系统进入救援模式或者是crtl D界面排查方法

如出现以下图片的情况可能需要修复磁盘&#xff1a; V10GFB-desktop&#xff1a; 开机后发现一致卡在此界面&#xff1a; 按esc键后有以下报错信息说明在/etc/fstab里面编写的外挂磁盘的命令有问题 解决方法如下&#xff1a;进入单用户模式对/etc/fstab进行修改&#xff1a; …
阅读更多...
proftpd安全加固：限制用户FTP登录

proftpd安全加固：限制用户FTP登录

其实无所谓安全加固&#xff0c;因为proftp默认就是限制用户FTP登录的&#xff0c;这里有点凌乱得研究和实验了proftpd如何进行限制的&#xff0c;以及可能的放开限制。懂了这些才能更好的进行防护配置。 RootLogin指令其实主要作用就是启用ROOT访问。通常&#xff0c;proftpd在…
阅读更多...
智能优化算法应用：基于广义正态分布算法无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用：基于广义正态分布算法无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于广义正态分布算法无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于广义正态分布算法无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.广义正态分布算法4.实验参数设定5.算…
阅读更多...
【教学类-35-06】17号的学号字帖延伸出的全体字帖（1-9去0）（A4竖版1份）

【教学类-35-06】17号的学号字帖延伸出的全体字帖（1-9去0）（A4竖版1份）

作品展示 背景需求&#xff1a; 给大4班17号同学单独做了一个学号字帖后&#xff0c;我想可以把这样的学具用在中班&#xff08;我马上要成为中4班老师了&#xff09;&#xff0c;那就需要给全班做一份这样的大号学号贴。 使用17号同学的word模板&#xff08;见下文&#xff…
阅读更多...
搭配君正主控芯片测评：创想三维物有所值，让你玩3D打印，而不是玩3D打印机

搭配君正主控芯片测评：创想三维物有所值，让你玩3D打印，而不是玩3D打印机

如果你在一年前开始接触3D打印&#xff0c;并且拥有一台入门级的3D打印机。那么&#xff0c;我相信很大一部分时间你是在给机器打“补丁”&#xff0c;让它真正能为你所用。而这台机器很可能是来自创想三维&#xff0c;不出意外就是其Ender系列的某一款。 然而&#xff0c;现在…
阅读更多...
【夯实技术基本功】「底层技术原理体系」全方位带你认识和透彻领悟正则表达式(Regular Expression)的开发手册（正则表达式定义 ）

【夯实技术基本功】「底层技术原理体系」全方位带你认识和透彻领悟正则表达式(Regular Expression)的开发手册（正则表达式定义 ）

【夯实技术基本功】「底层技术原理体系」全方位带你认识和透彻领悟正则表达式的开发手册 前提介绍正则表达式正则表达式的历史正则表达式的定义正则表达式的组成普通字符非打印字符特殊字符限定符限定符案例分析贪婪匹配/非贪婪匹配方式 定位符选择组合符后向引用 总结心得 前提…
阅读更多...
2024年安防视频监控行业将面临4大机遇和挑战

2024年安防视频监控行业将面临4大机遇和挑战

当前安防监控市场处于快速发展的阶段&#xff0c;市场不仅有传统的视频监控、门禁系统等单一功能的设备&#xff0c;还涌现出了一系列集成多种安防功能的综合系统。随着人工智能技术的发展&#xff0c;安防监控设备不仅可以对场所进行实时监控&#xff0c;还可以通过图像识别、…
阅读更多...
【STM32】蓝牙氛围灯

【STM32】蓝牙氛围灯

Docs 一、项目搭建和开发流程 一、项目需求和产品定义 1.需求梳理和产品定义 一般由甲方公司提出&#xff0c;或由本公司市场部提出 需求的重点是&#xff1a;这个产品究竟应该做成什么样&#xff1f;有哪些功能&#xff1f;具体要求和参数怎样&#xff1f;此外还要考虑售价…
阅读更多...
vue中组件传值方法

vue中组件传值方法

父组件给子组件传值 一、 1.在子组件标签中写入父组件传递数据 向下传递prop 2.在子组件内声明props选项接收父组件传递的数据 props:[,,] 父组件&#xff1a; <Header :msgmsg ></Header> 子组件&#xff1a; props:[msg], 二、 provide i…
阅读更多...
一个简单得爬虫小案例：获取西瓜网视频数据【python】

一个简单得爬虫小案例：获取西瓜网视频数据【python】

嗨喽~大家好呀&#xff0c;这里是魔王呐 ❤ ~! python更多源码/资料/解答/教程等 点击此处跳转文末名片免费获取 第三方模块: requests >>> pip install requests 环境介绍: python 3.8 解释器 pycharm 编辑器 思路分析 找到数据来源 你要爬取的视频 筛选 找不…
阅读更多...
第二十一章网络通信

第二十一章网络通信

网络程序设计基础 局域网与互联网 为了实现两台计算机的通信&#xff0c;必须用一个网络线路连接两台计算机。如下图所示 网络协议 1.IP协议 IP是Internet Protocol的简称&#xff0c;是一种网络协议。Internet 网络采用的协议是TCP/IP协议&#xff0c;其全称是Transmissio…
阅读更多...
最新文章

Copyright @ 2022~2023

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