廊坊论坛网站建设,惠山网页制作,官网站内推广内容,安徽省工程建设协会网站一、判断二叉树是否是完全二叉树/*** 判断二叉树是否是完全二叉树** //判断层序遍历过程如果节点有右子树 没有左子树 那么就不是完全二叉树* //判断层序遍历过程如果遇到第一个节点是没有左或右子树的#xff0c;也就是只有一个子节点或者没有#xff0c;那么再往后层序遍历…一、判断二叉树是否是完全二叉树/** * 判断二叉树是否是完全二叉树 * * //判断层序遍历过程如果节点有右子树 没有左子树 那么就不是完全二叉树 * //判断层序遍历过程如果遇到第一个节点是没有左或右子树的也就是只有一个子节点或者没有那么再往后层序遍历的节点都将是叶子节点否则就不是完全二叉树 */代码演示package class12;import java.util.LinkedList;
import java.util.Queue;/*** 判断二叉树是否是完全二叉树* p* //判断层序遍历过程如果节点有右子树 没有左子树 那么就不是完全二叉树* //判断层序遍历过程如果遇到第一个节点是没有左或右子树的也就是只有一个子节点或者没有那么再往后层序遍历的节点都将是叶子节点否则就不是完全二叉树*/
public class IsCBT {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value data;}}//方式一 完全二叉树是从上到下从左到右都是依次有节点//判断层序遍历过程如果节点有右子树 没有左子树 那么就不是完全二叉树//判断层序遍历过程如果遇到第一个节点是没有左或右子树的也就是只有一个子节点或者没有那么再往后层序遍历的节点都将是叶子节点否则就不是完全二叉树public static boolean isCBT1(Node head) {if (head null) {return true;}//层序遍历二叉树QueueNode queue new LinkedList();queue.add(head);//定义一个辅助变量记录当前弹出队列节点是否只有一个子节点或没有子节点如果是则赋值true,那么接着下次弹出的节点就肯定是叶子节点并且没有子节点这样才符合完全二叉树特性boolean flag false;while (!queue.isEmpty()) {//弹出队列节点head queue.poll();//记录当前节点的左右子节点Node left head.left;Node right head.right;//判断//如果 flag是true,表示上次弹出的节点的子节点不双全那么来到当前节点如果还存在有子节点就表示节点没有从左到右填充不是完全二叉树if ((flag (left ! null || right ! null))||//或者当前节点 左子节点空但右子节点非空 也不符合完全二叉树(left null right ! null)) {//则直接返回falsereturn false;}//接着判断左右子节点非空则入队列if (left ! null) {queue.add(left);}if (right ! null) {queue.add(right);}//判断当前弹出节点是否子节点不双全是的话就需要将falg赋值true 表示如果满足完全二叉树特性的话后续的都是叶子节点if (left null || right null) {flag true;}}//遍历后如果没有不符合的节点 那么就是完全二叉树返回truereturn true;}/*** 递归套路模板做法来判断是否十完全二叉树* 1假设以X节点为头假设可以向X左树和X右树要任何信息* 2在上一步的假设下讨论以X为头节点的树得到答案的可能性最重要* 3列出所有可能性后确定到底需要向左树和右树要什么样的信息* 4把左树信息和右树信息求全集就是任何一棵子树都需要返回的信息S* 5递归函数都返回S每一棵子树都这么要求* 6写代码在代码中考虑如何把左树的信息和右树信息整合出整棵树的信息*/public static boolean isCBT2(Node head) {//base case:空树也定义为完全二叉树 返回trueif (head null) {return true;}return process(head).isCBT;}//定义节点返回信息先分析题目需要判断以head节点的二叉树是否为完全二叉树那么需要我们判断这四种情况//1.节点左树和右树是满二叉树并且左树高度右树高度//2.节点左树是完全二叉树右数是满二叉树并且左树高度右树高度1//3.节点左树和右树是满二叉树并且左树高度右树高度1//4.节点左树是满二叉树右树是完全二叉树并且左树高度右树高度//符合这四种情况的二叉树都是完全二叉树 从中可以判断每个节点都需要带三个信息//是否是满二叉树是否是完全二叉树高度 接着利用 二叉树 后序遍历 左右根的递归序//这样才能满足从下往上返回给上节点信息。public static class Info {public boolean isFull;public boolean isCBT;public int height;public Info(boolean full, boolean cbt, int h) {isFull full;isCBT cbt;height h;}}//定义递归程序最终返回节点信息主函数调用返回isCBT属性值public static Info process(Node head) {if (head null) {//base case: 当递归到空节点的时候即返回空树的信息是满二叉树、是完全二叉树、高度0return new Info(true, true, 0);}//后序遍历 分别取左树 右树的信息Info leftInfo process(head.left);Info rightInfo process(head.right);//接着将当前节点的三个信息返回给上层节点isFull isCBT height 最后return封装到信息类//高度的获取当前节点高度就是其左树与右树最大高度树当前节点int height Math.max(leftInfo.height, rightInfo.height) 1;//是否满二叉树就是判断左树与右树是否是满二叉树,以及两子树高度相等boolean isFull leftInfo.isFull rightInfo.isFull leftInfo.height rightInfo.height;//是否完全二叉树在前面分析有四种情况符合其中一种就是完全二叉树初始值可以赋值false,符合再符合trueboolean isCBT false;if (isFull) {//情况11.节点左树和右树是满二叉树并且左树高度右树高度 其实就是判断是否是满二叉树直接引用前面的isFull的判断即可isCBT true;} else if (leftInfo.isCBT rightInfo.isFull leftInfo.height rightInfo.height 1) {//2.节点左树是完全二叉树右数是满二叉树并且左树高度右树高度1isCBT true;} else if(leftInfo.isFull rightInfo.isFull leftInfo.height rightInfo.height1){//3.节点左树和右树是满二叉树并且左树高度右树高度1isCBT true;}else if(leftInfo.isFull rightInfo.isCBT leftInfo.height rightInfo.height){//4.节点左树是满二叉树右树是完全二叉树并且左树高度右树高度isCBT true;}//最后将当前节点信息返回给上层节点return new Info(isFull,isCBT,height);}// for testpublic static Node generateRandomBST(int maxLevel, int maxValue) {return generate(1, maxLevel, maxValue);}// for testpublic static Node generate(int level, int maxLevel, int maxValue) {if (level maxLevel || Math.random() 0.5) {return null;}Node head new Node((int) (Math.random() * maxValue));head.left generate(level 1, maxLevel, maxValue);head.right generate(level 1, maxLevel, maxValue);return head;}public static void main(String[] args) {int maxLevel 5;int maxValue 100;int testTimes 1000000;for (int i 0; i testTimes; i) {Node head generateRandomBST(maxLevel, maxValue);if (isCBT1(head) ! isCBT2(head)) {System.out.println(Oops!);}}System.out.println(finish!);}
}
二、二叉树的递归套路1假设以X节点为头假设可以向X左树和X右树要任何信息2在上一步的假设下讨论以X为头节点的树得到答案的可能性最重要3列出所有可能性后确定到底需要向左树和右树要什么样的信息4把左树信息和右树信息求全集就是任何一棵子树都需要返回的信息S5递归函数都返回S每一棵子树都这么要求6写代码在代码中考虑如何把左树的信息和右树信息整合出整棵树的信息三、判断二叉树是否是搜索二叉树/** * 判断二叉树是否是搜索二叉树 中序遍历的节点大小是从小到大的顺序 * 1.左右子树是否为二叉搜索树 2.左子树的最大值要小于当前节点右子树的最小值要大于当前节点 * */package class12;import java.util.ArrayList;/*** 判断二叉树是否是搜索二叉树 中序遍历的节点大小是从小到大的顺序* 1.左右子树是否为二叉搜索树 2.左子树的最大值要小于当前节点右子树的最小值要大于当前节点**/
public class IsBST {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value data;}}public static boolean isBST1(Node head) {if (head null) {return true;}ArrayListNode arr new ArrayList();in(head, arr);for (int i 1; i arr.size(); i) {if (arr.get(i).value arr.get(i - 1).value) {return false;}}return true;}public static void in(Node head, ArrayListNode arr) {if (head null) {return;}in(head.left, arr);arr.add(head);in(head.right, arr);}public static boolean isBST2(Node head) {if (head null) {return true;}return process(head).isBST;}//节点返回信息判断是否为二叉搜索树就是判断// 1.左右子树是否为二叉搜索树 2.左子树的最大值要小于当前节点右子树的最小值要大于当前节点//所以我们定义每个节点都同等返回 是否二叉搜索树、最大最小值public static class Info {public boolean isBST;public int max;public int min;public Info(boolean i,int ma, int mi){isBST i;max ma;min mi;}}public static Info process(Node head){//节点空空树不好判断最大最小值所以我们可以返回给上层节点处理。这里就直接返回null,上层判断时//就需要注意判断空情况if(head null){return null;}//后序遍历因为要把下层节点都判断好是否为二叉搜索树再返回给根节点所以需要左右根的顺序Info leftInfo process(head.left);Info rightInfo process(head.right);//定义信息三个属性值 最大最小值默认当前节点值然后根据左右子树的最大最小值来刷新int max head.value;int min head.value;//如果左右子树非空各自都判断下最大最小值刷新值需要判空是因为前面空树情况我们返回null,避免空指针需要判空如果空就不用比较大小if(leftInfo ! null ){max Math.max(max,leftInfo.max);min Math.min(min,leftInfo.min);}if(rightInfo ! null ){max Math.max(max,rightInfo.max);min Math.min(min,rightInfo.min);}//判断是否是二叉搜索树 默认给trueboolean isBST true;//情况1左树非空并且左树不是二叉搜索树则当前节点树就不是二叉搜索树if(leftInfo ! null !leftInfo.isBST){isBST false;}//情况2右树非空并且右树不是二叉搜索树则当前节点树就不是二叉搜索树if(rightInfo ! null !rightInfo.isBST){isBST false;}//3.左树非空并且左树最大值大于等于当前节点 falseif(leftInfo ! null leftInfo.max head.value){isBST false;}//4.右树非空并且右树最小值小于等于当前节点 falseif(rightInfo ! null rightInfo.min head.value){isBST false;}return new Info(isBST,max,min);}// for testpublic static Node generateRandomBST(int maxLevel, int maxValue) {return generate(1, maxLevel, maxValue);}// for testpublic static Node generate(int level, int maxLevel, int maxValue) {if (level maxLevel || Math.random() 0.5) {return null;}Node head new Node((int) (Math.random() * maxValue));head.left generate(level 1, maxLevel, maxValue);head.right generate(level 1, maxLevel, maxValue);return head;}public static void main(String[] args) {int maxLevel 4;int maxValue 100;int testTimes 1000000;for (int i 0; i testTimes; i) {Node head generateRandomBST(maxLevel, maxValue);if (isBST1(head) ! isBST2(head)) {System.out.println(Oops!);}}System.out.println(finish!);}}
四、给定一棵二叉树的头节点head返回这颗二叉树是不是平衡二叉树/** * 给定一棵二叉树的头节点head返回这颗二叉树是不是平衡二叉树 * * 1.左右树平衡 2.左右树高度差不超过1 */package class12;/*** 给定一棵二叉树的头节点head返回这颗二叉树是不是平衡二叉树** 1.左右树平衡 2.左右树高度差不超过1*/
public class IsBalanced {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value data;}}public static boolean isBalanced1(Node head) {boolean[] ans new boolean[1];ans[0] true;process1(head, ans);return ans[0];}public static int process1(Node head, boolean[] ans) {if (!ans[0] || head null) {return -1;}int leftHeight process1(head.left, ans);int rightHeight process1(head.right, ans);if (Math.abs(leftHeight - rightHeight) 1) {ans[0] false;}return Math.max(leftHeight, rightHeight) 1;}public static boolean isBalanced2(Node head) {return process(head).isBalanced;}//二叉树返回节点信息是否是平衡需要判断左右树是否平衡以及左右树高度返回节点高度差不大于1是平衡则节点就是平衡树public static class Info {public boolean isBalanced;public int height;public Info(boolean isb, int h) {isBalanced isb;height h;}}//递归树程序返回头节点的节点信息public static Info process(Node head) {if (head null) {return new Info(true, 0);}//后序遍历左右根,分别取左右树的节点信息返回当前节点Info leftInfo process(head.left);Info rightInfo process(head.right);//定义当前节点的信息用于返回//高度左右树最高的子树高度加自身节点高度1int height Math.max(leftInfo.height, rightInfo.height) 1;//初始定义是平衡树boolean isBalanced true;//情况1如果左右树任意一个不是平衡树 那么这个节点树也就不是平衡树if (!leftInfo.isBalanced || !rightInfo.isBalanced) {isBalanced false;}//情况2左右树是平衡树高度差大于1 那么这个节点树就不是平衡树//情况1已经判断是否平衡子树所以这里可以省略能进判断说明肯定没进前面的判断是平衡子树if (Math.abs(leftInfo.height - rightInfo.height) 1) {isBalanced false;}return new Info(isBalanced, height);}// for testpublic static Node generateRandomBST(int maxLevel, int maxValue) {return generate(1, maxLevel, maxValue);}// for testpublic static Node generate(int level, int maxLevel, int maxValue) {if (level maxLevel || Math.random() 0.5) {return null;}Node head new Node((int) (Math.random() * maxValue));head.left generate(level 1, maxLevel, maxValue);head.right generate(level 1, maxLevel, maxValue);return head;}public static void main(String[] args) {int maxLevel 5;int maxValue 100;int testTimes 1000000;for (int i 0; i testTimes; i) {Node head generateRandomBST(maxLevel, maxValue);if (isBalanced1(head) ! isBalanced2(head)) {System.out.println(Oops!);}}System.out.println(finish!);}}五、给定一棵二叉树的头节点head返回这颗二叉树是不是满二叉树/** * 给定一棵二叉树的头节点head返回这颗二叉树是不是满二叉树 * 方法一 1. 2 ^ 层数 -1 树节点个数 * 方法二 1.是否左右子树是满二叉树 并且左右树高度相等 */package class12;/*** 给定一棵二叉树的头节点head返回这颗二叉树是不是满二叉树* 方法一 1. 2 ^ 层数 -1 树节点个数* 方法二 1.是否左右子树是满二叉树 并且左右树高度相等*/
public class IsFull {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value data;}}// 第一种方法// 收集整棵树的高度h和节点数n// 只有满二叉树满足 : 2 ^ h - 1 npublic static boolean isFull1(Node head) {if (head null) return true;//取出头节点的信息。然后按2 ^ h - 1 n 判断是否节点数是满二叉树Info1 isAll process1(head);return (1 isAll.height) - 1 isAll.nodes;}public static class Info1 {public int height;public int nodes;public Info1(int h, int n) {height h;nodes n;}}public static Info1 process1(Node head) {//空树则高度和节点都是0if (head null) {return new Info1(0, 0);}//后序遍历先取下层左右树的信息返回Info1 leftInfo process1(head.left);Info1 rightInfo process1(head.right);//定义当前节点的高度和节点树总个数int height Math.max(leftInfo.height, rightInfo.height) 1;int nodes leftInfo.nodes rightInfo.nodes 1;return new Info1(height, nodes);}//方法二是否左右子树是满二叉树 并且左右树高度相等public static boolean isFull2(Node head) {if (head null) {return true;}return process2(head).isFull;}public static class Info2 {public boolean isFull;public int height;public Info2(boolean isf, int h) {isFull isf;height h;}}public static Info2 process2(Node head) {if (head null) {return new Info2(true, 0);}//左右树取信息返回上层节点Info2 leftInfo process2(head.left);Info2 rightInfo process2(head.right);//获取当前节点大小。是否满二叉树int height Math.max(leftInfo.height, rightInfo.height) 1;boolean isFull leftInfo.isFull rightInfo.isFull leftInfo.height rightInfo.height;return new Info2(isFull,height);}// for testpublic static Node generateRandomBST(int maxLevel, int maxValue) {return generate(1, maxLevel, maxValue);}// for testpublic static Node generate(int level, int maxLevel, int maxValue) {if (level maxLevel || Math.random() 0.5) {return null;}Node head new Node((int) (Math.random() * maxValue));head.left generate(level 1, maxLevel, maxValue);head.right generate(level 1, maxLevel, maxValue);return head;}public static void main(String[] args) {int maxLevel 5;int maxValue 100;int testTimes 1000000;System.out.println(测试开始);for (int i 0; i testTimes; i) {Node head generateRandomBST(maxLevel, maxValue);if (isFull1(head) ! isFull2(head)) {System.out.println(出错了!);}}System.out.println(测试结束);}}六、给定一棵二叉树的头节点head返回这颗二叉树中最大的二叉搜索子树的大小/** * 给定一棵二叉树的头节点head * 返回这颗二叉树中最大的二叉搜索子树的大小 * * 目标是以某节点的树上的最大搜索子树 * 分大情况两种1.该节点的整棵树不是搜索树即该节点不做头节点 2.该节点的整棵树是搜索树。即该节点做头节点 * 1 那么结果就是 左右子树中最大的搜索树即为其所求最大搜索子树大小 * 2 以该节点的树是二叉搜索树 * ①左子树是二叉搜索树最大值小于该节点 * ②右子树是二叉搜索树最小值大于该节点 * ③都是二叉搜索树后则取左右子树的大小求和再将加该节点1 得到这个最大搜索树大小 返回 * * 分情况后分析节点是需要哪些数据 * 1.最大二叉搜索子树的大小 * 2.是否是二叉搜索树 * 3.树的最大值 * 4.树的最小值 * 5.树的大小 * * 这里可以合并一个信息就是如果 15的情况下那么就表示该树是二叉搜索树所以2可以省略掉 */package class12;/*** 给定一棵二叉树的头节点head* 返回这颗二叉树中最大的二叉搜索子树的大小** 目标是以某节点的树上的最大搜索子树* 分大情况两种1.该节点的整棵树不是搜索树即该节点不做头节点 2.该节点的整棵树是搜索树。即该节点做头节点* 1 那么结果就是 左右子树中最大的搜索树即为其所求最大搜索子树大小* 2 以该节点的树是二叉搜索树* ①左子树是二叉搜索树最大值小于该节点* ②右子树是二叉搜索树最小值大于该节点* ③都是二叉搜索树后则取左右子树的大小求和再将加该节点1 得到这个最大搜索树大小 返回** 分情况后分析节点是需要哪些数据* 1.最大二叉搜索子树的大小* 2.是否是二叉搜索树* 3.树的最大值* 4.树的最小值* 5.树的大小** 这里可以合并一个信息就是如果 15的情况下那么就表示该树是二叉搜索树所以2可以省略掉*/public class MaxSubBSTSize {// 提交时不要提交这个类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){//空树返回0if(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 head){if(head null){//因为节点返回的存在最大最小值空树的时候不好设置就直接返回null,给到上层处理并且需要注意要判空再处理避免空指针异常return null;}//后序遍历左右根取左右子树信息返回Info leftInfo process(head.left);Info rightInfo process(head.right);//返回当前节点的四个信息, 最大子树大小比较复杂需要判断再赋值int max head.val;int min head.val;int allSize 1;//根据左右子树非空来依次刷新当前节点的三个值if (leftInfo ! null){max Math.max(max,leftInfo.max);min Math.min(min, leftInfo.min);allSize leftInfo.allSize;}if (rightInfo ! null){max Math.max(max,rightInfo.max);min Math.min(min, rightInfo.min);allSize rightInfo.allSize;}//接着判断几种情况分别比较其大小取最大的二叉搜索子树大小返回int p1 -1;//情况1当前节点整棵树不是二叉搜索树且左子树非空那么就返回该左子树的最大二叉搜索子树大小if(leftInfo ! null ){p1 leftInfo.maxBSTSubtreeSize;}int p2 -1;//情况2当前节点整棵树不是二叉搜索树且右子树非空那么就返回该右子树的最大二叉搜索子树大小if(rightInfo ! null ){p2 rightInfo.maxBSTSubtreeSize;}int p3 -1;//情况3当前节点整棵树是二叉搜索树进行判断//先判断左右子树是否是二叉搜索树//如果树空空树也是二叉搜索树返回true,非空则判断是否是二叉搜索树前面提到如果最大搜索子树大小当前树大小就说明是二叉搜索树boolean leftBST leftInfo null ? true : (leftInfo.maxBSTSubtreeSize leftInfo.allSize);boolean rightBST rightInfo null ? true : (rightInfo.maxBSTSubtreeSize rightInfo.allSize);if(leftBST rightBST){//如果左右子树都是二叉搜索树就判断整个树是否是二叉搜索树 注意判空则直接true非空左树最大值小于当前节点右树最小值大于当前节点boolean leftMaxLessX leftInfo null ? true : (leftInfo.max head.val);boolean rightMinMoreX rightInfo null ? true : (rightInfo.min head.val);if(leftMaxLessX rightMinMoreX){//符合的话那么就表示当前树是二叉搜索树刷新p3值大小注意判空空则返回0非空 就等于左右子树的allSize求和1int leftSize leftInfo null ? 0 : leftInfo.allSize;int rightSize rightInfo null ? 0 : rightInfo.allSize;//当前节点为二叉搜索树那么最大二叉搜索子树就是自己大小就是左右树大小求和自身1p3 leftSize rightSize 1;}}//最后比较三种情况的二叉搜索子树的大小取最大返回return new Info(Math.max(p1, Math.max(p2,p3)),allSize,max,min);}}
七、给定一棵二叉树的头节点head任何两个节点之间都存在距离返回整棵二叉树的最大距离/** * 给定一棵二叉树的头节点head任何两个节点之间都存在距离表示经过多少个节点 也就是树高 * 返回整棵二叉树的最大距离 * * 1.最大距离没有经过头节点head * 取左树中最大距离 右树中最大距离 * * 2.最大距离经过头节点head * 取左树最远节点到头节点高度即左树高度 右树最远节点到头节点高度即右树高度 再加头节点 1 * * 取其中最大值返回 */package class12;import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;/*** 给定一棵二叉树的头节点head任何两个节点之间都存在距离表示经过多少个节点 也就是树高* 返回整棵二叉树的最大距离** 1.最大距离没有经过头节点head* 取左树中最大距离 右树中最大距离** 2.最大距离经过头节点head* 取左树最远节点到头节点高度即左树高度 右树最远节点到头节点高度即右树高度 再加头节点 1** 取其中最大值返回*/
public class MaxDistance {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value data;}}public static int maxDistance1(Node head) {if (head null) {return 0;}ArrayListNode arr getPrelist(head);HashMapNode, Node parentMap getParentMap(head);int max 0;for (int i 0; i arr.size(); i) {for (int j i; j arr.size(); j) {max Math.max(max, distance(parentMap, arr.get(i), arr.get(j)));}}return max;}public static ArrayListNode getPrelist(Node head) {ArrayListNode arr new ArrayList();fillPrelist(head, arr);return arr;}public static void fillPrelist(Node head, ArrayListNode arr) {if (head null) {return;}arr.add(head);fillPrelist(head.left, arr);fillPrelist(head.right, arr);}public static HashMapNode, Node getParentMap(Node head) {HashMapNode, Node map new HashMap();map.put(head, null);fillParentMap(head, map);return map;}public static void fillParentMap(Node head, HashMapNode, Node parentMap) {if (head.left ! null) {parentMap.put(head.left, head);fillParentMap(head.left, parentMap);}if (head.right ! null) {parentMap.put(head.right, head);fillParentMap(head.right, parentMap);}}public static int distance(HashMapNode, Node parentMap, Node o1, Node o2) {HashSetNode o1Set new HashSet();Node cur o1;o1Set.add(cur);while (parentMap.get(cur) ! null) {cur parentMap.get(cur);o1Set.add(cur);}cur o2;while (!o1Set.contains(cur)) {cur parentMap.get(cur);}Node lowestAncestor cur;cur o1;int distance1 1;while (cur ! lowestAncestor) {cur parentMap.get(cur);distance1;}cur o2;int distance2 1;while (cur ! lowestAncestor) {cur parentMap.get(cur);distance2;}return distance1 distance2 - 1;}public static int maxDistance2(Node head){if(head null) return 0;return process(head).maxDistance;}//返回节点信息需要有最大距离和高度返回上节点public static class Info{public int maxDistance;public int height;public Info(int m, int h){maxDistance m;height h;}}public static Info process(Node head){if(head null){//空树那么直接返回最大距离和高度都是0return new Info(0,0);}//后序遍历取左右节点信息返回当前节点使用Info leftInfo process(head.left);Info rightInfo process(head.right);//获取当前节点的高度信息和最大距离最大距离需要分情况判断后比较大小返回最大int height Math.max(leftInfo.height,rightInfo.height)1;//最大距离分三种情况//情况1最大距离没经过当前节点取左树最大距离int p1 leftInfo.maxDistance;//情况2最大距离没经过当前节点取右树最大距离int p2 rightInfo.maxDistance;//情况3最大距离经过当前节点取左树高度右树高度当前节点1int p3 leftInfo.height rightInfo.height 1;return new Info(Math.max(p1, Math.max(p2,p3)),height);}// for testpublic static Node generateRandomBST(int maxLevel, int maxValue) {return generate(1, maxLevel, maxValue);}// for testpublic static Node generate(int level, int maxLevel, int maxValue) {if (level maxLevel || Math.random() 0.5) {return null;}Node head new Node((int) (Math.random() * maxValue));head.left generate(level 1, maxLevel, maxValue);head.right generate(level 1, maxLevel, maxValue);return head;}public static void main(String[] args) {int maxLevel 4;int maxValue 100;int testTimes 1000000;for (int i 0; i testTimes; i) {Node head generateRandomBST(maxLevel, maxValue);if (maxDistance1(head) ! maxDistance2(head)) {System.out.println(Oops!);}}System.out.println(finish!);}
}
八、给定一棵二叉树的头节点head返回这颗二叉树中最大的二叉搜索子树的头节点package class13;import java.util.ArrayList;/*** 给定一棵二叉树的头节点head* 返回这颗二叉树中最大的二叉搜索子树的头节点*/
public class MaxSubBSTHead {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value data;}}public static int getBSTSize(Node head) {if (head null) {return 0;}ArrayListNode arr new ArrayList();in(head, arr);for (int i 1; i arr.size(); i) {if (arr.get(i).value arr.get(i - 1).value) {return 0;}}return arr.size();}public static void in(Node head, ArrayListNode arr) {if (head null) {return;}in(head.left, arr);arr.add(head);in(head.right, arr);}public static Node maxSubBSTHead1(Node head) {if (head null) {return null;}if (getBSTSize(head) ! 0) {return head;}Node leftAns maxSubBSTHead1(head.left);Node rightAns maxSubBSTHead1(head.right);return getBSTSize(leftAns) getBSTSize(rightAns) ? leftAns : rightAns;}public static Node maxSubBSTHead2(Node head) {if (head null) return null;return process(head).maxSubBSTHead;}//返回节点信息public static class Info {public Node maxSubBSTHead;public int maxSubBSTSize;public int max;public int min;public Info(Node ma, int size, int m, int mi) {maxSubBSTHead ma;maxSubBSTSize size;max m;min mi;}}public static Info process(Node head) {if (head null) {//空树不好判断最大最小值就返回空返回给上层节点处理。需要注意判空处理return null;}//后序遍历获取左右子树信息Info leftInfo process(head.left);Info rightInfo process(head.right);//定义当前节点属性信息int max head.value;int min head.value;Node maxSubBSTHead null;int maxSubBSTSize 0;//左右树不空刷新属性信息。// 两种情况1 2同步按 左右子树其一是最大二叉搜索树的两种情况进行赋值maxSubBSTHeadif (leftInfo ! null) {max Math.max(max, leftInfo.max);min Math.min(min, leftInfo.min);//左树非空先定义最大二叉搜索树头节点和大小是其左树的值maxSubBSTHead leftInfo.maxSubBSTHead;maxSubBSTSize leftInfo.maxSubBSTSize;}if (rightInfo ! null) {max Math.max(max, rightInfo.max);min Math.min(min, rightInfo.min);//刷新最大头节点前提是如果右树的大小是大于左树的 再重新赋值if (rightInfo.maxSubBSTSize maxSubBSTSize) {maxSubBSTHead rightInfo.maxSubBSTHead;maxSubBSTSize rightInfo.maxSubBSTSize;}}//情况3 当前节点树是最大二叉搜索树返回该节点//判断子树是否空空则为二叉搜索树返回true 非空则判断 子树最大二叉搜索树头节点是否对应当前节点树的子节点并且符合左树最大值小于当前节点右树最小值大于当前节点if ((leftInfo null || (leftInfo.maxSubBSTHead head.left leftInfo.max head.value)) (rightInfo null || (rightInfo.maxSubBSTHead head.right rightInfo.min head.value))) {//符合则刷新最大二叉搜索树节点和大小 大小就是左右树大小和1maxSubBSTHead head;maxSubBSTSize (leftInfo null ? 0 : leftInfo.maxSubBSTSize) (rightInfo null ? 0 : rightInfo.maxSubBSTSize) 1;}return new Info(maxSubBSTHead,maxSubBSTSize,max,min);}// for testpublic static Node generateRandomBST(int maxLevel, int maxValue) {return generate(1, maxLevel, maxValue);}// for testpublic static Node generate(int level, int maxLevel, int maxValue) {if (level maxLevel || Math.random() 0.5) {return null;}Node head new Node((int) (Math.random() * maxValue));head.left generate(level 1, maxLevel, maxValue);head.right generate(level 1, maxLevel, maxValue);return head;}public static void main(String[] args) {int maxLevel 4;int maxValue 100;int testTimes 1000000;for (int i 0; i testTimes; i) {Node head generateRandomBST(maxLevel, maxValue);if (maxSubBSTHead1(head) ! maxSubBSTHead2(head)) {System.out.println(Oops!);}}System.out.println(finish!);}
}
九、给定一棵二叉树的头节点head和另外两个节点a和b。返回a和b的最低公共祖先/** * 给定一棵二叉树的头节点head和另外两个节点a和b。 * 返回a和b的最低公共祖先 * p * 分析情况 * 1.最低公共祖先不在head: * 在左树中找到a b 最低公共祖先那么将该ans节点往上返回给头节点 * 在右树找到同理返回上层 * 2.最低公共祖先在head: * 那么肯定 a b 分别都能在子树中找到 * p * 这里注意找 a b 节点除了在节点的子树找之外也要判断当前节点是否为a b 可能递归到相等的时候 */package class13;import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;/*** 给定一棵二叉树的头节点head和另外两个节点a和b。* 返回a和b的最低公共祖先* p* 分析情况* 1.最低公共祖先不在head:* 在左树中找到a b 最低公共祖先那么将该ans节点往上返回给头节点* 在右树找到同理返回上层* 2.最低公共祖先在head:* 那么肯定 a b 分别都能在子树中找到* p* 这里注意找 a b 节点除了在节点的子树找之外也要判断当前节点是否为a b 可能递归到相等的时候*/public class LowestAncestor {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value data;}}public static Node lowestAncestor1(Node head, Node o1, Node o2) {if (head null) {return null;}// key的父节点是valueHashMapNode, Node parentMap new HashMap();parentMap.put(head, null);fillParentMap(head, parentMap);HashSetNode o1Set new HashSet();Node cur o1;o1Set.add(cur);while (parentMap.get(cur) ! null) {cur parentMap.get(cur);o1Set.add(cur);}cur o2;while (!o1Set.contains(cur)) {cur parentMap.get(cur);}return cur;}public static void fillParentMap(Node head, HashMapNode, Node parentMap) {if (head.left ! null) {parentMap.put(head.left, head);fillParentMap(head.left, parentMap);}if (head.right ! null) {parentMap.put(head.right, head);fillParentMap(head.right, parentMap);}}public static Node lowestAncestor2(Node head, Node a, Node b) {if (head null) return null;return process(head, a, b).ans;}//返回节点的信息是否找到a b 节点是否存在最低公共祖先节点public static class Info {public boolean findA;public boolean findB;public Node ans;public Info(boolean a, boolean b, Node an) {findA a;findB b;ans an;}}public static Info process(Node head, Node a, Node b) {if(head null){//空树则是不回找到ab节点false也没有最低祖先nullreturn new Info(false,false,null);}//后序遍历 取左右树信息Info leftInfo process(head.left,a,b);Info rightInfo process(head.right,a,b);//给当前节点属性信息赋值返回//判断当前节点是否是ab节点以及左右子树是否找到了ab节点boolean findA a head || leftInfo.findA || rightInfo.findA;boolean findB b head || leftInfo.findB || rightInfo.findB;//判断是否是最低祖先。//情况1不在当前节点 在子树子树非空那么就是其最低祖先节点属性Node ans null;if(leftInfo.ans ! null){ans leftInfo.ans;}else if(rightInfo.ans ! null){ans rightInfo.ans;}//情况2当前节点是最低祖先那么就是当前节点树能找到ab节点返回当前节点else if(findA findB){ans head;}return new Info(findA,findB,ans);}// for testpublic static Node generateRandomBST(int maxLevel, int maxValue) {return generate(1, maxLevel, maxValue);}// for testpublic static Node generate(int level, int maxLevel, int maxValue) {if (level maxLevel || Math.random() 0.5) {return null;}Node head new Node((int) (Math.random() * maxValue));head.left generate(level 1, maxLevel, maxValue);head.right generate(level 1, maxLevel, maxValue);return head;}// for testpublic static Node pickRandomOne(Node head) {if (head null) {return null;}ArrayListNode arr new ArrayList();fillPrelist(head, arr);int randomIndex (int) (Math.random() * arr.size());return arr.get(randomIndex);}// for testpublic static void fillPrelist(Node head, ArrayListNode arr) {if (head null) {return;}arr.add(head);fillPrelist(head.left, arr);fillPrelist(head.right, arr);}public static void main(String[] args) {int maxLevel 4;int maxValue 100;int testTimes 1000000;for (int i 0; i testTimes; i) {Node head generateRandomBST(maxLevel, maxValue);Node o1 pickRandomOne(head);Node o2 pickRandomOne(head);if (lowestAncestor1(head, o1, o2) ! lowestAncestor2(head, o1, o2)) {System.out.println(Oops!);}}System.out.println(finish!);}}
十、派对的最大快乐值员工信息的定义如下:class Employee { public int happy; // 这名员工可以带来的快乐值 ListEmployee subordinates; // 这名员工有哪些直接下级}公司的每个员工都符合 Employee 类的描述。整个公司的人员结构可以看作是一棵标准的、没有环的多叉树。树的头节点是公司唯一的老板。除老板之外的每个员工都有唯一的直接上级。 叶节点是没有任何下属的基层员工(subordinates列表为空)除基层员工外每个员工都有一个或多个直接下级。这个公司现在要办party你可以决定哪些员工来哪些员工不来规则1.如果某个员工来了那么这个员工的所有直接下级都不能来2.派对的整体快乐值是所有到场员工快乐值的累加3.你的目标是让派对的整体快乐值尽量大给定一棵多叉树的头节点boss请返回派对的最大快乐值。* //分情况* 1.当前节点来参加 那么下层节点就都不能参加 快乐值0* 2.当前节点不来参加 那么下层节点可参加可不参加取两者快乐值最大package class13;
/*** 派对的最大快乐值** 员工信息的定义如下:* class Employee {* public int happy; // 这名员工可以带来的快乐值* ListEmployee subordinates; // 这名员工有哪些直接下级* }* 派对的最大快乐值* 公司的每个员工都符合 Employee 类的描述。整个公司的人员结构可以看作是一棵标准的、 没有环的多叉树。树的头节点是公司唯一的老板。* 除老板之外的每个员工都有唯一的直接上级。 叶节点是没有任何下属的基层员工(subordinates列表为空)除基层员工外每个员工都有一个或多个直接下级。* 这个公司现在要办party你可以决定哪些员工来哪些员工不来规则* 1.如果某个员工来了那么这个员工的所有直接下级都不能来* 2.派对的整体快乐值是所有到场员工快乐值的累加* 3.你的目标是让派对的整体快乐值尽量大* 给定一棵多叉树的头节点boss请返回派对的最大快乐值。*** //分情况* 1.当前节点来参加 那么下层节点就都不能参加 快乐值0* 2.当前节点不来参加 那么下层节点可参加可不参加取两者快乐值最大*/import java.util.ArrayList;
import java.util.List;public class MaxHappy {public static class Employee {public int happy;public ListEmployee nexts;public Employee(int h) {happy h;nexts new ArrayList();}}public static int maxHappy1(Employee boss) {if (boss null) {return 0;}return process1(boss, false);}// 当前来到的节点叫cur// up表示cur的上级是否来// 该函数含义// 如果up为true表示在cur上级已经确定来的情况下cur整棵树能够提供最大的快乐值是多少// 如果up为false表示在cur上级已经确定不来的情况下cur整棵树能够提供最大的快乐值是多少public static int process1(Employee cur, boolean up) {if (up) { // 如果cur的上级来的话cur没得选只能不来int ans 0;for (Employee next : cur.nexts) {ans process1(next, false);}return ans;} else { // 如果cur的上级不来的话cur可以选可以来也可以不来int p1 cur.happy;int p2 0;for (Employee next : cur.nexts) {p1 process1(next, true);p2 process1(next, false);}return Math.max(p1, p2);}}public static int maxHappy2(Employee boss) {//接收boss节点 参加与不参加的两种情况再返回最大值Info allInfo process(boss);return Math.max(allInfo.no,allInfo.yes);}//返回信息即根节点来的快乐值 不来的快乐值public static class Info{public int no;public int yes;public Info(int n, int y){no n;yes y;}}public static Info process(Employee cur){if(cur null){//空节点也就是没有员工那么更没有参加与否的快乐值 0return new Info(0,0);}//设置属性 no 没参加 那么快乐值就是0 yes 参加 快乐值就是自身int no 0;int yes cur.happy;for(Employee next:cur.nexts){//多叉树往下递归Info nextInfo process(next);//刷新no值如果当前节点no 不参加那么nextInfo子节点 参加或不参加都可以所以快乐值取两种情况较大值no Math.max(nextInfo.no,nextInfo.yes);//刷新yes值当前节点参加那么子节点不能参加快乐值0yes nextInfo.no;}return new Info(no,yes);}// for testpublic static Employee genarateBoss(int maxLevel, int maxNexts, int maxHappy) {if (Math.random() 0.02) {return null;}Employee boss new Employee((int) (Math.random() * (maxHappy 1)));genarateNexts(boss, 1, maxLevel, maxNexts, maxHappy);return boss;}// for testpublic static void genarateNexts(Employee e, int level, int maxLevel, int maxNexts, int maxHappy) {if (level maxLevel) {return;}int nextsSize (int) (Math.random() * (maxNexts 1));for (int i 0; i nextsSize; i) {Employee next new Employee((int) (Math.random() * (maxHappy 1)));e.nexts.add(next);genarateNexts(next, level 1, maxLevel, maxNexts, maxHappy);}}public static void main(String[] args) {int maxLevel 4;int maxNexts 7;int maxHappy 100;int testTimes 100000;for (int i 0; i testTimes; i) {Employee boss genarateBoss(maxLevel, maxNexts, maxHappy);if (maxHappy1(boss) ! maxHappy2(boss)) {System.out.println(Oops!);}}System.out.println(finish!);}}
