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

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

本文主要是介绍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 - 1for (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;}}

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


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

相关文章

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”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2