做搜狗网站排名软件,做电路方案设计的网站,万网买的网站备案吗,北京建筑公司class036 二叉树高频题目-上-不含树型dp code1 102. 二叉树的层序遍历
// 二叉树的层序遍历 // 测试链接 : https://leetcode.cn/problems/binary-tree-level-order-traversal/
code1 普通bfs code2 一次操作一层
package class036;import java.util.ArrayList;
import java…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 ListListInteger levelOrder1(TreeNode root) {ListListInteger ans new ArrayList();if (root ! null) {QueueTreeNode queue new LinkedList();HashMapTreeNode, 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 ListListInteger levelOrder2(TreeNode root) {ListListInteger ans new ArrayList();if (root ! null) {l r 0;queue[r] root;while (l r) { // 队列里还有东西int size r - l;ArrayListInteger list new ArrayListInteger();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 ListListInteger zigzagLevelOrder(TreeNode root) {ListListInteger ans new ArrayList();if (root ! null) {l r 0;queue[r] root;// false 代表从左往右// true 代表从右往左boolean reverse false; while (l r) {int size r - l;ArrayListInteger list new ArrayListInteger();// 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;}HashMapInteger, 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, HashMapInteger, 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;}}
