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

class036 二叉树高频题目-上-不含树型dp

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

code1 102. 二叉树的层序遍历

// 二叉树的层序遍历
// 测试链接 : https://leetcode.cn/problems/binary-tree-level-order-traversal/

code1 普通bfs
code2 一次操作一层

package class036;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

// 二叉树的层序遍历
// 测试链接 : https://leetcode.cn/problems/binary-tree-level-order-traversal/
public class Code01_LevelOrderTraversal {

	// 不提交这个类
	public static class TreeNode {
		public int val;
		public TreeNode left;
		public TreeNode right;
	}

	// 提交时把方法名改为levelOrder,此方法为普通bfs,此题不推荐
	public static List<List<Integer>> levelOrder1(TreeNode root) {
		List<List<Integer>> ans = new ArrayList<>();
		if (root != null) {
			Queue<TreeNode> queue = new LinkedList<>();
			HashMap<TreeNode, Integer> levels = new HashMap<>();
			queue.add(root);
			levels.put(root, 0);
			while (!queue.isEmpty()) {
				TreeNode cur = queue.poll();
				int level = levels.get(cur);
				if (ans.size() == level) {
					ans.add(new ArrayList<>());
				}
				ans.get(level).add(cur.val);
				if (cur.left != null) {
					queue.add(cur.left);
					levels.put(cur.left, level + 1);
				}
				if (cur.right != null) {
					queue.add(cur.right);
					levels.put(cur.right, level + 1);
				}
			}
		}
		return ans;
	}

	// 如果测试数据量变大了就修改这个值
	public static int MAXN = 2001;

	public static TreeNode[] queue = new TreeNode[MAXN];

	public static int l, r;

	// 提交时把方法名改为levelOrder,此方法为每次处理一层的优化bfs,此题推荐
	public static List<List<Integer>> levelOrder2(TreeNode root) {
		List<List<Integer>> ans = new ArrayList<>();
		if (root != null) {
			l = r = 0;
			queue[r++] = root;
			while (l < r) { // 队列里还有东西
				int size = r - l;
				ArrayList<Integer> list = new ArrayList<Integer>();
				for (int i = 0; i < size; i++) {
					TreeNode cur = queue[l++];
					list.add(cur.val);
					if (cur.left != null) {
						queue[r++] = cur.left;
					}
					if (cur.right != null) {
						queue[r++] = cur.right;
					}
				}
				ans.add(list);
			}
		}
		return ans;
	}

}

code2 103. 二叉树的锯齿形层序遍历

// 二叉树的锯齿形层序遍历
// 测试链接 : https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/

code 遍历

package class036;

import java.util.ArrayList;
import java.util.List;

// 二叉树的锯齿形层序遍历
// 测试链接 : https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/
public class Code02_ZigzagLevelOrderTraversal {

	// 不提交这个类
	public static class TreeNode {
		public int val;
		public TreeNode left;
		public TreeNode right;
	}

	// 提交以下的方法
	// 用每次处理一层的优化bfs就非常容易实现
	// 如果测试数据量变大了就修改这个值
	public static int MAXN = 2001;

	public static TreeNode[] queue = new TreeNode[MAXN];

	public static int l, r;

	public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
		List<List<Integer>> ans = new ArrayList<>();
		if (root != null) {
			l = r = 0;
			queue[r++] = root;
			// false 代表从左往右
			// true 代表从右往左
			boolean reverse = false; 
			while (l < r) {
				int size = r - l;
				ArrayList<Integer> list = new ArrayList<Integer>();
				// reverse == false, 左 -> 右, l....r-1, 收集size个
				// reverse == true,  右 -> 左, r-1....l, 收集size个
				// 左 -> 右, i = i + 1
				// 右 -> 左, i = i - 1
				for (int i = reverse ? r - 1 : l, j = reverse ? -1 : 1, k = 0; k < size; i += j, k++) {
					TreeNode cur = queue[i];
					list.add(cur.val);
				}
				for (int i = 0; i < size; i++) {
					TreeNode cur = queue[l++];
					if (cur.left != null) {
						queue[r++] = cur.left;
					}
					if (cur.right != null) {
						queue[r++] = cur.right;
					}
				}
				ans.add(list);
				reverse = !reverse;
			}
		}
		return ans;
	}

}

code3 662. 二叉树最大宽度

// 二叉树的最大特殊宽度
// 测试链接 : https://leetcode.cn/problems/maximum-width-of-binary-tree/

package class036;

// 二叉树的最大特殊宽度
// 测试链接 : https://leetcode.cn/problems/maximum-width-of-binary-tree/
public class Code03_WidthOfBinaryTree {

	// 不提交这个类
	public static class TreeNode {
		public int val;
		public TreeNode left;
		public TreeNode right;
	}

	// 提交以下的方法
	// 用每次处理一层的优化bfs就非常容易实现
	// 如果测试数据量变大了就修改这个值
	public static int MAXN = 3001;

	public static TreeNode[] nq = new TreeNode[MAXN];

	public static int[] iq = new int[MAXN];

	public static int l, r;

	public static int widthOfBinaryTree(TreeNode root) {
		int ans = 1;
		l = r = 0;
		nq[r] = root;
		iq[r++] = 1;
		while (l < r) {
			int size = r - l;
			ans = Math.max(ans, iq[r - 1] - iq[l] + 1);
			for (int i = 0; i < size; i++) {
				TreeNode node = nq[l];
				int id = iq[l++];
				if (node.left != null) {
					nq[r] = node.left;
					iq[r++] = id * 2;
				}
				if (node.right != null) {
					nq[r] = node.right;
					iq[r++] = id * 2 + 1;
				}
			}
		}
		return ans;
	}

}

code4 104. 二叉树的最大深度 111. 二叉树的最小深度

// 求二叉树的最大、最小深度
// 测试链接 : https://leetcode.cn/problems/maximum-depth-of-binary-tree/
// 测试链接 : https://leetcode.cn/problems/minimum-depth-of-binary-tree/

package class036;

// 求二叉树的最大、最小深度
public class Code04_DepthOfBinaryTree {

	// 不提交这个类
	public static class TreeNode {
		public int val;
		public TreeNode left;
		public TreeNode right;
	}

	// 测试链接 : https://leetcode.cn/problems/maximum-depth-of-binary-tree/
	public static int maxDepth(TreeNode root) {
		return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
	}

	// 测试链接 : https://leetcode.cn/problems/minimum-depth-of-binary-tree/
	public int minDepth(TreeNode root) {
		if (root == null) {
			// 当前的树是空树
			return 0;
		}
		if (root.left == null && root.right == null) {
			// 当前root是叶节点
			return 1;
		}
		int ldeep = Integer.MAX_VALUE;
		int rdeep = Integer.MAX_VALUE;
		if (root.left != null) {
			ldeep = minDepth(root.left);
		}
		if (root.right != null) {
			rdeep = minDepth(root.right);
		}
		return Math.min(ldeep, rdeep) + 1;
	}

}

code5 297. 二叉树的序列化与反序列化

// 二叉树先序序列化和反序列化
// 测试链接 : https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/

package class036;

// 二叉树先序序列化和反序列化
// 测试链接 : https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/
public class Code05_PreorderSerializeAndDeserialize {

	// 不提交这个类
	public static class TreeNode {
		public int val;
		public TreeNode left;
		public TreeNode right;

		public TreeNode(int v) {
			val = v;
		}
	}

    // 二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化
    // 但是,二叉树无法通过中序遍历的方式实现序列化和反序列化
    // 因为不同的两棵树,可能得到同样的中序序列,即便补了空位置也可能一样。
    // 比如如下两棵树
    //         __2
    //        /
    //       1
    //       和
    //       1__
    //          \
    //           2
    // 补足空位置的中序遍历结果都是{ null, 1, null, 2, null}
	// 提交这个类
	public class Codec {

		public String serialize(TreeNode root) {
			StringBuilder builder = new StringBuilder();
			f(root, builder);
			return builder.toString();
		}

		void f(TreeNode root, StringBuilder builder) {
			if (root == null) {
				builder.append("#,");
			} else {
				builder.append(root.val + ",");
				f(root.left, builder);
				f(root.right, builder);
			}
		}

		public TreeNode deserialize(String data) {
			String[] vals = data.split(",");
			cnt = 0;
			return g(vals);
		}

		// 当前数组消费到哪了
		public static int cnt;

		TreeNode g(String[] vals) {
			String cur = vals[cnt++];
			if (cur.equals("#")) {
				return null;
			} else {
				TreeNode head = new TreeNode(Integer.valueOf(cur));
				head.left = g(vals);
				head.right = g(vals);
				return head;
			}
		}

	}

}

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

// 利用先序与中序遍历序列构造二叉树
// 测试链接 : https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

package class036;

// 二叉树按层序列化和反序列化
// 测试链接 : https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/
public class Code06_LevelorderSerializeAndDeserialize {

	// 不提交这个类
	public static class TreeNode {
		public int val;
		public TreeNode left;
		public TreeNode right;

		public TreeNode(int v) {
			val = v;
		}
	}

	// 提交这个类
	// 按层序列化
	public class Codec {

		public static int MAXN = 10001;

		public static TreeNode[] queue = new TreeNode[MAXN];

		public static int l, r;

		public String serialize(TreeNode root) {
			StringBuilder builder = new StringBuilder();
			if (root != null) {
				builder.append(root.val + ",");
				l = 0;
				r = 0;
				queue[r++] = root;
				while (l < r) {
					root = queue[l++];
					if (root.left != null) {
						builder.append(root.left.val + ",");
						queue[r++] = root.left;
					} else {
						builder.append("#,");
					}
					if (root.right != null) {
						builder.append(root.right.val + ",");
						queue[r++] = root.right;
					} else {
						builder.append("#,");
					}
				}
			}
			return builder.toString();
		}

		public TreeNode deserialize(String data) {
			if (data.equals("")) {
				return null;
			}
			String[] nodes = data.split(",");
			int index = 0;
			TreeNode root = generate(nodes[index++]);
			l = 0;
			r = 0;
			queue[r++] = root;
			while (l < r) {
				TreeNode cur = queue[l++];
				cur.left = generate(nodes[index++]);
				cur.right = generate(nodes[index++]);
				if (cur.left != null) {
					queue[r++] = cur.left;
				}
				if (cur.right != null) {
					queue[r++] = cur.right;
				}
			}
			return root;
		}

		private TreeNode generate(String val) {
			return val.equals("#") ? null : new TreeNode(Integer.valueOf(val));
		}

	}

}

code7 958. 二叉树的完全性检验

// 验证完全二叉树
// 测试链接 : https://leetcode.cn/problems/check-completeness-of-a-binary-tree/

1)无左有右 flase
2)孩子不全开始 必须都是叶子结点,否则false

package class036;

import java.util.HashMap;

// 利用先序与中序遍历序列构造二叉树
// 测试链接 : https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
public class Code07_PreorderInorderBuildBinaryTree {

	// 不提交这个类
	public static class TreeNode {
		public int val;
		public TreeNode left;
		public TreeNode right;

		public TreeNode(int v) {
			val = v;
		}
	}

	// 提交如下的方法
	public static TreeNode buildTree(int[] pre, int[] in) {
		if (pre == null || in == null || pre.length != in.length) {
			return null;
		}
		HashMap<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < in.length; i++) {
			map.put(in[i], i);
		}
		return f(pre, 0, pre.length - 1, in, 0, in.length - 1, map);
	}

	public static TreeNode f(int[] pre, int l1, int r1, int[] in, int l2, int r2, HashMap<Integer, Integer> map) {
		if (l1 > r1) {
			return null;
		}
		TreeNode head = new TreeNode(pre[l1]);
		if (l1 == r1) {
			return head;
		}
		int k = map.get(pre[l1]);
		// pre : l1(........)[.......r1]
		// in  : (l2......)k[........r2]
		// (...)是左树对应,[...]是右树的对应
		head.left = f(pre, l1 + 1, l1 + k - l2, in, l2, k - 1, map);
		head.right = f(pre, l1 + k - l2 + 1, r1, in, k + 1, r2, map);
		return head;
	}

}

code8 222. 完全二叉树的节点个数

// 求完全二叉树的节点个数
// 测试链接 : https://leetcode.cn/problems/count-complete-tree-nodes/

package class036;

// 验证完全二叉树
// 测试链接 : https://leetcode.cn/problems/check-completeness-of-a-binary-tree/
public class Code08_CompletenessOfBinaryTree {

	// 不提交这个类
	public static class TreeNode {
		public int val;
		public TreeNode left;
		public TreeNode right;
	}

	// 提交以下的方法
	// 如果测试数据量变大了就修改这个值
	public static int MAXN = 101;

	public static TreeNode[] queue = new TreeNode[MAXN];

	public static int l, r;

	public static boolean isCompleteTree(TreeNode h) {
		if (h == null) {
			return true;
		}
		l = r = 0;
		queue[r++] = h;
		// 是否遇到过左右两个孩子不双全的节点
		boolean leaf = false;
		while (l < r) {
			h = queue[l++];
			if ((h.left == null && h.right != null) || (leaf && (h.left != null || h.right != null))) {
				return false;
			}
			if (h.left != null) {
				queue[r++] = h.left;
			}
			if (h.right != null) {
				queue[r++] = h.right;
			}
			if (h.left == null || h.right == null) {
				leaf = true;
			}
		}
		return true;
	}

}

code9 222. 完全二叉树的节点个数

// 求完全二叉树的节点个数
// 测试链接 : https://leetcode.cn/problems/count-complete-tree-nodes/

package class036;

// 求完全二叉树的节点个数
// 测试链接 : https://leetcode.cn/problems/count-complete-tree-nodes/
public class Code09_CountCompleteTreeNodes {

	// 不提交这个类
	public static class TreeNode {
		public int val;
		public TreeNode left;
		public TreeNode right;
	}

	// 提交如下的方法
	public static int countNodes(TreeNode head) {
		if (head == null) {
			return 0;
		}
		return f(head, 1, mostLeft(head, 1));
	}

	// cur : 当前来到的节点
	// level :  当前来到的节点在第几层
	// h : 整棵树的高度,不是cur这棵子树的高度
	// 求 : cur这棵子树上有多少节点
	public static int f(TreeNode cur, int level, int h) {
		if (level == h) {
			return 1;
		}
		if (mostLeft(cur.right, level + 1) == h) {
			// cur右树上的最左节点,扎到了最深层
			return (1 << (h - level)) + f(cur.right, level + 1, h);
		} else {
			// cur右树上的最左节点,没扎到最深层
			return (1 << (h - level - 1)) + f(cur.left, level + 1, h);
		}
	}

	// 当前节点是cur,并且它在level层
	// 返回从cur开始不停往左,能扎到几层
	public static int mostLeft(TreeNode cur, int level) {
		while (cur != null) {
			level++;
			cur = cur.left;
		}
		return level - 1;
	}

}

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

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

相关文章

9. 使用Pthreads实现线程池(一)

背景 多线程的一个典型应用场景就是服务器的并发处理,如下图所示,多名用户向服务器发出数据操作的请求。为了提高并发性,我们可以在每收到一个用户请求时就创建一个线程处理相关操作。这种操作在请求数量较少时没有什么问题,但在请求数量很多时你会发现线程的创建和销毁所占…

绑定域名简单教程

&#x1f4d1;打牌 &#xff1a; da pai ge的个人主页 &#x1f324;️个人专栏 &#xff1a; da pai ge的博客专栏 ☁️宝剑锋从磨砺出&#xff0c;梅花香自苦寒来 &#x1f324;️安装Nginx环境 &…

第七次作业

1&#xff0c; 给定一个包含n1个整数的数组nums&#xff0c;其数字在1到n之间&#xff08;包含1和n)&#xff0c;可知至少存在一个重复的整数&#xff0c;假设只有一个重复的整数&#xff0c;请找出这个重复的数 arr input("") num [int(n) for n in arr.split()]…

mysql 5.7 Unknown column ‘password‘ in ‘field list‘

问题现象&#xff1a; 执行sql : select user&#xff0c;host,password from user&#xff1b;时提示 ERROR 1054(42S22):Unknown column password in field list 现象如下图所示&#xff1a; mysql 5.7开始 密码字段用&#xff1a;authentication_string

http接口自动化测试框架实现

一、测试需求描述 对服务后台一系列的http接口功能测试。 输入&#xff1a;根据接口描述构造不同的参数输入值 输出&#xff1a;XML文件 eg:http://xxx.com/xxx_product/test/content_book_list.jsp?listid1 二、实现方法 1、选用Python脚本来驱动测试 2、采用Excel表格…

【hacker送书第10期】AI时代系列丛书(五选一)

AI时代系列丛书 AI时代程序员开发之道✨内容简介参与方式 AI时代项目经理成长之道✨内容简介参与方式 AI时代架构师修炼之道✨内容简介参与方式 AI时代产品经理升级之道✨内容简介参与方式 AI时代Python量化交易实战✨内容简介参与方式 AI时代程序员开发之道✨ 内容简介 本书是…

zabbix配置snmp trap--使用snmptrapd和Bash接收器--图文教程

1.前言 我的zabbix的版本是5.0版本&#xff0c;5.0的官方文档没有使用bash接收器的示例&#xff0c;6.0的官方文档有使用bash接收器的示例&#xff0c;但是&#xff0c;下载文件的链接失效&#xff1f;&#xff01; 这里讲解zabbix-server端配置和zabbix web端配置 2.zabbix-…

好用免费的AI换脸5个工具

在当今社会的发展中&#xff0c;人工智能&#xff08;Artificial Intelligence, AI&#xff09;扮演着关键的角色&#xff0c;其应用领域不断扩展。作为AI的一个分支&#xff0c;换脸技术近年来备受欢迎。这项技术使得将一个人的面部特征迁移到另一个人的照片或视频成为可能。除…

链式二叉树的创建及遍历(数据结构实训)

题目&#xff1a; 链式二叉树的创建及遍历 描述&#xff1a; 树的遍历有先序遍历、中序遍历和后序遍历。先序遍历的操作定义是先访问根结点&#xff0c;然后访问左子树&#xff0c;最后访问右子树。中序遍历的操作定义是先访问左子树&#xff0c;然后访问根&#xff0c;最后访问…

Ubuntu宝塔面板本地部署轻论坛系统HadSky并远程访问

文章目录 前言1. 网站搭建1.1 网页下载和安装1.2 网页测试1.3 cpolar的安装和注册 2. 本地网页发布2.1 Cpolar临时数据隧道2.2 Cpolar稳定隧道&#xff08;云端设置&#xff09;2.3 Cpolar稳定隧道&#xff08;本地设置&#xff09;2.4 公网访问测试 总结 前言 经过多年的基础…

【python、opencv】opencv仿射变换原理及代码实现

opencv仿射变换原理 仿射变换是opencv的基本知识点&#xff0c;主要目的是将原始图片经过仿射变换矩阵&#xff0c;平移、缩放、旋转成目标图像。用数学公式表示就是坐标转换。 其中x&#xff0c;y是原始图像坐标&#xff0c;u&#xff0c;v是变换后的图像坐标。将公式转换为…

深入Os--动态链接

1.动态链接库的使用 动态库支持以两种模式使用&#xff0c;一种模式下&#xff0c;在程序加载运行时&#xff0c;完成动态链接。一种模式下&#xff0c;在程序运行中&#xff0c;完成动态链接。 1.1.程序加载运行时完成动态链接 我们通过一个实例介绍程序加载运行时&#xff0c…

深入理解Dubbo-1.初识Dubbo

&#x1f44f;作者简介&#xff1a;大家好&#xff0c;我是爱吃芝士的土豆倪&#xff0c;24届校招生Java选手&#xff0c;很高兴认识大家&#x1f4d5;系列专栏&#xff1a;Spring源码、JUC源码、Kafka原理、分布式技术原理&#x1f525;如果感觉博主的文章还不错的话&#xff…

12.7作业

1. #include "mywidget.h"MyWidget::MyWidget(QWidget *parent): QWidget(parent) {//***********窗口相关设置***********//设置窗体大小this->resize(540,410);this->setFixedSize(540,410);//取消菜单栏this->setWindowFlag(Qt::FramelessWindowHint);/…

【数据库】基于时间戳的并发访问控制,乐观模式,时间戳替代形式及存在的问题,与封锁模式的对比

使用时间戳的并发控制 ​专栏内容&#xff1a; 手写数据库toadb 本专栏主要介绍如何从零开发&#xff0c;开发的步骤&#xff0c;以及开发过程中的涉及的原理&#xff0c;遇到的问题等&#xff0c;让大家能跟上并且可以一起开发&#xff0c;让每个需要的人成为参与者。 本专栏会…

MySQL之binlog文件过多处理方法

背景 MySQL由于大量读写&#xff0c;导致binlog文件特别的多。从而导致服务器disk空间不足问题。 先备份binlog文件 tar -zcvf mysql.tar.gz mysql/data/mysql-bin.00* 修改MySQL配置 binlog过期时间 show variables like expire_logs_days; 这里 0 表示 永不过期 如果为 n…

LeedCode刷题---双指针问题(二)

顾得泉&#xff1a;个人主页 个人专栏&#xff1a;《Linux操作系统》 《C/C》 《LeedCode刷题》 键盘敲烂&#xff0c;年薪百万&#xff01; 一、盛水最多的容器 题目链接&#xff1a;盛最多水的容器 题目描述 给定一个长度为 n 的整数数组 height 。有 n 条垂线&#xf…

Nacos下载、启动与使用的保姆级教程!

nacos下载及启动 nacos下载 首先打开nacos官方仓库链接。Nacos发布版本仓库。 点击Tags按钮找到nacos的历史发布的所有版本&#xff0c;点击download。 然后选择需要的下载即可。 后缀为.tar.gz为linux系统上运行的压缩包 后缀为.zip为windows系统上运行的压缩包 zip格式的…

vivado时序方法检查5

TIMING-14 &#xff1a; 时钟树上的 LUT 在时钟树上发现 LUT <cell_name> 。不建议在时钟路径上包含 LUT 单元。 描述 时钟路径上的 LUT 可能导致偏差过大 &#xff0c; 因为时钟必须在穿过互连结构的常规布线资源上进行布线。除偏差过大外 &#xff0c; 这些路径更…

[论文阅读]BEVFusion

BEVFusion BEVFusion: A Simple and Robust LiDAR-Camera Fusion Framework BEVFusion&#xff1a;简单而强大的激光雷达相机融合框架 论文网址&#xff1a;BEVFusion 论文代码&#xff1a;BEVFusion 简读论文 论文背景&#xff1a;激光雷达和摄像头是自动驾驶系统中常用的两…