分销网站有哪些,微网站开发教材,没人做网站了吗,网站推广做招商加盟判断二叉树是否是完全二叉树 思路#xff1a;层次遍历#xff0c;如果之前某个节点叶子节点为空#xff0c;队列后续的所有节点的左右节点都不能非空#xff0c;并且如果节点左节点为null但是右节点不为null该二叉树一定不是满二叉树
public static boolean isCBT1(Node … 判断二叉树是否是完全二叉树 思路层次遍历如果之前某个节点叶子节点为空队列后续的所有节点的左右节点都不能非空并且如果节点左节点为null但是右节点不为null该二叉树一定不是满二叉树
public static boolean isCBT1(Node head) {// PCif(head null)return true;LinkedListNode queue new LinkedList();boolean isLeaf false;queue.add(head);while (!queue.isEmpty()){Node cur queue.poll();Node left cur.left;Node right cur.right;if((isLeaf (left ! null || right ! null)) || (left null right ! null))return false;if(left ! null ){queue.add(left);}if(right ! null){queue.add(right);}if(left null || right null)isLeaf true;}return true;}思路2使用递归方式返回以当前节点为头结点的二叉树是否是满二叉树|完全二叉树以及返回当前树高度调用方根据左右子树返回的信息判断当前树是否为完全二叉树
// 使用递归方式public static boolean isCBT2(class13.Code01_IsCBT.Node head) {if(head null)return true;Info process process(head);return process.isc;}public static Info process(Node head){if (head null){return new Info(true,true,0);}Info l process(head.left);Info r process(head.right);boolean isFull l.isf r.isf l.height r.height;int height Math.max(l.height,r.height)1;boolean isComplate false;if(l.height r.height){if((l.isf r.isf)||(l.isf r.isc)){isComplate true;}}else {if(l.height r.height1){if((r.isf l.isf)||(r.isf l.isc)){isComplate true;}}}return new Info(isComplate,isFull,height);}static class Info{// 也包括满二叉树场景private boolean isc;private boolean isf;private int height;public Info(boolean isc,boolean isf,int height){this.isc isc;this.isf isf;this.height height;}}题目给定一棵二叉树的头节点head和另外两个节点a和b。返回a和b的最低公共祖先 思路先序遍历二叉树过程中记录子节点的父节点维护在Map类型参数中然后求第一个相同的祖先
方法2递归返回当前节点左右子树是否包含指定节点如果是直接返回否则根据返回内容处理
static class Info{boolean finda;boolean findb;Node ans ;public Info(boolean finda, boolean findb, Node ans) {this.finda finda;this.findb findb;this.ans ans;}}public static Node lowestAncestor1(Node head, Node o1, Node o2) {// PCInfo ans process(head, o1, o2);return ans.ans;}public static Info process(Node head, Node o1, Node o2){if(head null)return new Info(false,false,null);Info l process(head.left,o1,o2);Info r process(head.right,o1,o2);boolean finda head o1?true:l.finda||r.finda;boolean findb head o2?true:r.findb||l.findb;Node ans null;if(l.ans ! null){ans l.ans;}else if (r.ans ! null){ans r.ans;}else {if(finda findb){ans head;}}return new Info(finda,findb,ans);}题目派对的最大快乐值 公司的每个员工都符合 Employee 类的描述。整个公司的人员结构可以看作是一棵标准的、 没有环的多叉树。树的头节点是公司唯一的老板。除老板之外的每个员工都有唯一的直接上级。 叶节点是没有任何下属的基层员工(subordinates列表为空)除基层员工外每个员工都有一个或多个直接下级。派对的最大快乐值这个公司现在要办party你可以决定哪些员工来哪些员工不来规则1.如果某个员工来了那么这个员工的所有直接下级都不能来2.派对的整体快乐值是所有到场员工快乐值的累加3.你的目标是让派对的整体快乐值尽量大给定一棵多叉树的头节点boss请返回派对的最大快乐值。 思路递归实现
public static int maxHappy1(Employee boss) {// PCif(boss null)return 0;return Math.max(process(boss,true),process(boss,false));}// cur 来到当前人员// exist 直接领导是否来// 返回最大快乐值public static int process(Employee cur,boolean exist){if(cur null)return 0;// 当前人员选择不来 这种情况和上级领导来或者不来都不影响int no 0;for (Employee next : cur.nexts) {no process(next,false);}int yes 0;// 上级领未来并且当前人员参加if(!exist){for (Employee next : cur.nexts) {yes process(next,true);}yes cur.happy;}return Math.max(yes,no);}上面递归方式传递参数包含了上级是否参加信息另外一种递归方式返回当前人员参加或者不参加两种情况的最大值由上级决定自己是否参加
static class Info {private int no;private int yes;public Info(int no, int yes) {this.no no;this.yes yes;}}public static int maxHappy2(Employee boss) {if (boss null)return 0;Info info process2(boss);return Math.max(info.yes, info.no);}// 返回当前人员参加或者不参加最大happy值// 具体如何使用由上层决定public static Info process2(Employee cur) {if (cur null)return new Info(0, 0);int yes cur.happy;int no 0;for (Employee next : cur.nexts) {Info info process2(next);no Math.max(info.no, info.yes);yes info.no;}return new Info(no, yes);}题目判断二叉树是否是搜索二叉树 方法1递归左右子树返回是否递归相关信息调用方法根据返回信息判断
public static boolean isBST1(Node head) {if(head null)return true;Info info process(head);return info.isSearch;}// 以当前节点为根节的二叉树返回是否搜索二叉树信息public static Info process(Node head){Info left null;if(head.left ! null){left process(head.left);}Info right null;if(head.right ! null){right process(head.right);}int max head.value;int min head.value;if(left ! null){max Math.max(max, left.max);min Math.min(min, left.min);}if(right ! null){max Math.max(right.max,max);min Math.min(min, right.min);}boolean flag true;if(left ! null !left.isSearch)flag false;if(right ! null !right.isSearch)flag false;if(left ! null left.max head.value)flag false;if(right!null right.min head.value){flag false;}return new Info(max,min,flag);}static class Info{private int max;private int min;private boolean isSearch;public Info(int max, int min, boolean isSearch) {this.max max;this.min min;this.isSearch isSearch;}}方法2利用二叉搜索树性质先序遍历一定是递增序列 题目给定一棵二叉树的头节点head返回这颗二叉树是不是平衡二叉树 思路递归方法
public static boolean isBalanced1(Node head) {if(head null)return true;Info ans process(head);return ans.isblance;}// 以当前节点为根节点的二叉树返回该二叉树是否为平衡二叉树public static Info process(Node head){if(head null)return new Info(true,0);Info l process(head.left);Info r process(head.right);boolean is false;// 不管左右子树是否为平衡二叉树 直接计算调用方最终需要的不是高度而是 是否平衡int height Math.max(l.height,r.height)1;// process方法返回对象一定不为nullif(l.isblance r.isblance Math.abs(l.height-r.height)1){is true;}return new Info(is,height);}static class Info {private boolean isblance;private Integer height ;public Info(boolean isblance, Integer height) {this.isblance isblance;this.height height;}}题目给定一棵二叉树的头节点head返回这颗二叉树是不是满二叉树 思路层次遍历上一层和当前层数量二倍关系特殊情况最后一层遍历时候需要特殊处理
public static boolean isFull1(Node head) {if(head null)return true;// 层次遍历 判断上一层和当前层数量是否二倍关系LinkedListNode queue new LinkedList();queue.add(head);while (!queue.isEmpty()){// 用于判断是否为最后一行boolean allNull true;int pre queue.size();for (int i 0; i pre; i) {Node cur queue.poll();if(cur.left ! null){queue.add(cur.left);allNull false;}if(cur.right ! null){queue.add(cur.right);allNull false;}}int nextlen queue.size();// 不是最后一行name上一层和当前层节点数量一定是二倍关系if(!allNull nextlen ! 2*pre){return false;}}return true;}思路2:递归方法返回左右子树是否为满二叉树
static class Info{private boolean isFull;private int height ;public Info(boolean isFull, int height) {this.isFull isFull;this.height height;}}public static boolean isFull2(Node head) {if(head null)return true;Info process process(head);return process.isFull;}public static Info process(Node head){if(head null){return new Info(true,0);}Info l process(head.left);Info r process(head.right);boolean isFull false;int height Math.max(l.height,r.height)1;if(l.isFull r.isFull l.height r.height){isFull true;}return new Info(isFull,height);}题目给定一棵二叉树的头节点head返回这颗二叉树中最大的二叉搜索子树的大小 思路递归返回子树作为根节点二叉搜索树信息、
public static class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int value) {val value;}}// 提交如下的代码可以直接通过public static int largestBSTSubtree(TreeNode head) {if (head null) {return 0;}return process(head).maxBSTSubtreeSize;}public static class Info {public int maxBSTSubtreeSize;public int allSize;public int max;public int min;public Info(int m, int a, int ma, int mi) {maxBSTSubtreeSize m;allSize a;max ma;min mi;}}public static Info process(TreeNode x) {if (x null) {return null;}Info leftInfo process(x.left);Info rightInfo process(x.right);int max x.val;int min x.val;int allSize 1;if (leftInfo ! null) {max Math.max(leftInfo.max, max);min Math.min(leftInfo.min, min);allSize leftInfo.allSize;}if (rightInfo ! null) {max Math.max(rightInfo.max, max);min Math.min(rightInfo.min, min);allSize rightInfo.allSize;}int p1 -1;if (leftInfo ! null) {p1 leftInfo.maxBSTSubtreeSize;}int p2 -1;if (rightInfo ! null) {p2 rightInfo.maxBSTSubtreeSize;}int p3 -1;boolean leftBST leftInfo null ? true : (leftInfo.maxBSTSubtreeSize leftInfo.allSize);boolean rightBST rightInfo null ? true : (rightInfo.maxBSTSubtreeSize rightInfo.allSize);if (leftBST rightBST) {boolean leftMaxLessX leftInfo null ? true : (leftInfo.max x.val);boolean rightMinMoreX rightInfo null ? true : (x.val rightInfo.min);if (leftMaxLessX rightMinMoreX) {int leftSize leftInfo null ? 0 : leftInfo.allSize;int rightSize rightInfo null ? 0 : rightInfo.allSize;p3 leftSize rightSize 1;}}return new Info(Math.max(p1, Math.max(p2, p3)), allSize, max, min);} 题目给定一棵二叉树的头节点head任何两个节点之间都存在距离 返回整棵二叉树的最大距离 思路递归方法最大宽度要么经过当前节点要么是左右子树任意一个最长路径
public static Info process(Node head){if(head null){return null;}Info left process(head.left);Info right process(head.right);// 最大宽度经过当前head节点int has 1;int maxwide 0;int depth 0;if(left ! null){has left.maxdepth;maxwide Math.max(left.maxwide,maxwide);depth Math.max(depth,left.maxdepth);}if(right ! null){has right.maxdepth;maxwide Math.max(right.maxwide,maxwide);depth Math.max(depth,right.maxdepth);}// 最大宽度要么经过当前节点要么在左右任意子树maxwide Math.max(has,maxwide);return new Info(depth1,maxwide);}static class Info{// 最大深度private int maxdepth;// 最大宽度private int maxwide;public Info(int maxdepth, int maxwide) {this.maxdepth maxdepth;this.maxwide maxwide;}}问题给定字符串数组返回所有组合中字典排序最小的组合对应的字符串 思路1 暴力方法获取所有排列组合然后取字典排序最小的
// process 拿到所有的排列租户然后找到最小的一个并返回public static String lowestString1(String[] strs) {// PCif (strs null || strs.length 0) return ;TreeSetString process process(strs);return process.size() 0 ? : process.first();}// 返回当前数组 arrs 的所有组合public static TreeSetString process(String[] arrs) {TreeSetString ans new TreeSet();if (arrs null || arrs.length 0) {ans.add();return ans;}for (int i 0; i arrs.length; i) {String[] strings removeIndex(arrs, i);TreeSetString process process(strings);for (String string : process) {ans.add(arrs[i] string);}}return ans;}public static String[] removeIndex(String[] arrs, int index) {int N arrs.length;String[] ans new String[N-1];int j 0;for (int i 0; i arrs.length; i) {if (i index) continue;ans[j] arrs[i];}return ans;}方法2 贪心算法维护优先队列将目标字符串元素加入队列最终的队列即使字典排序最小的组合。优先队列指定比较器
public static String lowestString2(String[] strs) {if (strs null || strs.length 0) return ;// 1 优先队列 将元素依次放入Arrays.sort(strs,new ComparatorString() {Overridepublic int compare(String o1, String o2) {return (o1 o2).compareTo(o2 o1);}});// 2 最终的队列就是结果StringBuilder sb new StringBuilder();for (String str : strs) {sb.append(str);}return sb.toString();}需要注意的是往队列塞入元素时候如果在比较i位置元素时候就确定大小顺序i之前的所有元素是不会进行比较的,所以这里存在一个问题咋判断当前插入元素和i之前的元素组合就不是最小的。论证如下 递推法
队列初始有两个字符串 a b 并且 ab 字典序小于 ba 所以a排在b前面
当前字符串c需要进入队列和b进行比较字典序大于b所以排在b后面
比较a 和 c的字典序
字符串ac可以转换为 N(a)*M(c)N(c) K进制的数字 其中M(c): Math.sqrt(K,c.length) N(a) 为字符串a对应的K进制数字
字符串ca可以转换为 N(c)*M(a)N(a)
现在需要求 N(c)*M(a)N(a) N(a)*M(c)N(c)
已知
abba
N(a)*M(b)N(b) N(b)*M(a)N(a) 公式1
bccb
N(b)*M(c)N(c) N(c)*M(b)N(b) 公式2 公式1 两边同时减去 N(b) 后同时乘 N(c) 因为数字不为负数所以不改变比较符号
N(a)*M(b)*N(c) N(c)*N(b)*M(a) N(a)*N(c) - N(b)*N(c) 公式3
公式2 两边同时减去 N(b) 后同时乘 N(a) 因为数字不为负数所以不改变比较符号
N(b)*M(c)*N(a) N(c)*N(a)-N(b)*N(a) N(c)*M(b)*N(a) 公式4
公式3 左边等于公式4右边 整理得
N(b)*M(c)*N(a) N(c)*N(a)-N(b)*N(a) N(c)*N(b)*M(a) N(a)*N(c) - N(b)*N(c)
N(b)*M(c)*N(a)-N(b)*N(a) N(c)*N(b)*M(a)- N(b)*N(c)
M(c)*N(a) -N(a) N(c)*M(a) -N(c)
M(c)*N(a) N(c) N(c)*M(a) N(a)
最终得
acca
所以得到结论abba 并且 bccb 那么 ac 一定小于 ca如果队列前面有n个已排序字符串 现在往里面塞 字符串 s并且 arr[n-1]s sarr[n-1]
那么可以得到 [0,n-1) 和字符串 s 存在这样的关系 Str(0,n-2)s s Str(0,n-2)
其中Str(0,n-2) 为[0,n-2] 范围任意长度字符串组合最终得到结论按照代码Comparator方式插入队列后最终的队列就是字典序最小的组合
