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

2023-12-07 23:01
文章标签 算法 二叉树 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/467643。

相关文章

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

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

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “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]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
hdu4826（三维DP）

hdu4826（三维DP）

这是一个百度之星的资格赛第四题 题目链接：http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意：从左上角的点到右上角的点，每个点只能走一遍，走的方向有三个：向上，向下，向右，求最大值。 咋一看像搜索题，先暴搜，TLE,然后剪枝，还是TLE.然后我就改方法，用DP来做，这题和普通dp相比，多个个向上
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
hdu1011（背包树形DP）

hdu1011（背包树形DP）

没有完全理解这题， m个人，攻打一个map，map的入口是1，在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下： #include<iostream>#include<algorithm
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
hdu4865(概率DP)

hdu4865(概率DP)

题意：已知前一天和今天的天气概率，某天的天气概率和叶子的潮湿程度的概率，n天叶子的湿度，求n天最有可能的天气情况。 思路：概率DP，dp[i][j]表示第i天天气为j的概率，状态转移如下：dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下： #include <stdio.h>#include
阅读更多...
usaco 1.1 Broken Necklace（DP）

usaco 1.1 Broken Necklace（DP）

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于： 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2