【算法&数据结构体系篇class12、13】：二叉树

迈不过友情╰ 2024-03-26 16:31 47阅读 0赞

### 一、判断二叉树是否是完全二叉树 ###

> */\*\**  
>  *\* 判断二叉树是否是完全二叉树*  
>  *\**  
>  *\* //判断层序遍历过程如果节点有右子树 没有左子树 那么就不是完全二叉树*  
>  *\* //判断层序遍历过程如果遇到第一个节点是没有左或右子树的，也就是只有一个子节点或者没有，那么再往后层序遍历的节点都将是叶子节点，否则就不是完全二叉树*  
>  *\*/*

**代码演示：**

package class12;
 
 import java.util.LinkedList;
 import java.util.Queue;
 
 /**
 * 判断二叉树是否是完全二叉树
 * 
 * //判断层序遍历过程如果节点有右子树 没有左子树 那么就不是完全二叉树
 * //判断层序遍历过程如果遇到第一个节点是没有左或右子树的，也就是只有一个子节点或者没有，那么再往后层序遍历的节点都将是叶子节点，否则就不是完全二叉树
 */
 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;
 }
 //层序遍历二叉树
 Queue<Node> 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)
 ) {
 //则直接返回false
 return false;
 }
 //接着判断左右子节点，非空则入队列
 if (left != null) {
 queue.add(left);
 }
 if (right != null) {
 queue.add(right);
 }
 //判断当前弹出节点是否子节点不双全，是的话就需要将falg赋值true 表示如果满足完全二叉树特性的话，后续的都是叶子节点
 if (left == null || right == null) {
 flag = true;
 }
 }
 //遍历后如果没有不符合的节点 那么就是完全二叉树，返回true
 return true;
 }
 
 
 /**
 * 递归套路模板做法来判断是否十完全二叉树
 * 1）假设以X节点为头，假设可以向X左树和X右树要任何信息
 * 2）在上一步的假设下，讨论以X为头节点的树，得到答案的可能性（最重要）
 * 3）列出所有可能性后，确定到底需要向左树和右树要什么样的信息
 * 4）把左树信息和右树信息求全集，就是任何一棵子树都需要返回的信息S
 * 5）递归函数都返回S，每一棵子树都这么要求
 * 6）写代码，在代码中考虑如何把左树的信息和右树信息整合出整棵树的信息
 */
 public static boolean isCBT2(Node head) {
 //base case:空树，也定义为完全二叉树 返回true
 if (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: 当递归到空节点的时候，即返回空树的信息，是满二叉树、是完全二叉树、高度0
 return 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,符合再符合true
 boolean isCBT = false;
 if (isFull) {
 //情况1：1.节点左树和右树是满二叉树，并且左树高度=右树高度 其实就是判断是否是满二叉树，直接引用前面的isFull的判断即可
 isCBT = true;
 } else if (leftInfo.isCBT && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
 //2.节点左树是完全二叉树，右数是满二叉树，并且左树高度=右树高度+1
 isCBT = true;
 } else if(leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height+1){
 //3.节点左树和右树是满二叉树，并且左树高度=右树高度+1
 isCBT = true;
 }else if(leftInfo.isFull && rightInfo.isCBT && leftInfo.height == rightInfo.height){
 //4.节点左树是满二叉树，右树是完全二叉树，并且左树高度=右树高度
 isCBT = true;
 }
          //最后将当前节点信息返回给上层节点
 return new Info(isFull,isCBT,height);
 }
 
 
 // for test
 public static Node generateRandomBST(int maxLevel, int maxValue) {
 return generate(1, maxLevel, maxValue);
 }
 
 // for test
 public 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）把左树信息和右树信息求全集，就是任何一棵子树都需要返回的信息S  
> 5）递归函数都返回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;
 }
 ArrayList<Node> 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, ArrayList<Node> 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);
 }
 //判断是否是二叉搜索树 默认给true
 boolean isBST = true;
 //情况1：左树非空，并且左树不是二叉搜索树，则当前节点树就不是二叉搜索树
 if(leftInfo != null && !leftInfo.isBST){
 isBST = false;
 }
 //情况2：右树非空，并且右树不是二叉搜索树，则当前节点树就不是二叉搜索树
 if(rightInfo != null && !rightInfo.isBST){
 isBST = false;
 }
 //3.左树非空，并且左树最大值大于等于当前节点 false
 if(leftInfo != null && leftInfo.max >= head.value){
 isBST = false;
 }
 //4.右树非空，并且右树最小值小于等于当前节点 false
 if(rightInfo != null && rightInfo.min <= head.value){
 isBST = false;
 }
 return new Info(isBST,max,min);
 }
 
 // for test
 public static Node generateRandomBST(int maxLevel, int maxValue) {
 return generate(1, maxLevel, maxValue);
 }
 
 // for test
 public 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);
 //定义当前节点的信息，用于返回
 //高度，左右树最高的子树高度加自身节点高度1
 int 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 test
 public static Node generateRandomBST(int maxLevel, int maxValue) {
 return generate(1, maxLevel, maxValue);
 }
 
 // for test
 public 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 == n
 public 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) {
 //空树，则高度和节点都是0
 if (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 test
 public static Node generateRandomBST(int maxLevel, int maxValue) {
 return generate(1, maxLevel, maxValue);
 }
 
 // for test
 public 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.树的大小*  
>  *\**  
>  *\* 这里可以合并一个信息，就是如果 1==5的情况下，那么就表示该树是二叉搜索树，所以2可以省略掉*  
>  *\*/*

package class12;
 
 /**
 * 给定一棵二叉树的头节点head，
 * 返回这颗二叉树中最大的二叉搜索子树的大小
 *
 * 目标是以某节点的树上的最大搜索子树
 * 分大情况两种：1.该节点的整棵树不是搜索树，即该节点不做头节点 2.该节点的整棵树是搜索树。即该节点做头节点
 * 1： 那么结果就是 左右子树中最大的搜索树即为其所求最大搜索子树大小
 * 2： 以该节点的树是二叉搜索树：
 * ①左子树是二叉搜索树，最大值小于该节点；
 * ②右子树是二叉搜索树，最小值大于该节点；
 * ③都是二叉搜索树后，则取左右子树的大小求和再将加该节点+1 得到这个最大搜索树大小 返回
 *
 * 分情况后分析节点是需要哪些数据：
 * 1.最大二叉搜索子树的大小
 * 2.是否是二叉搜索树
 * 3.树的最大值
 * 4.树的最小值
 * 5.树的大小
 *
 * 这里可以合并一个信息，就是如果 1==5的情况下，那么就表示该树是二叉搜索树，所以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){
 //空树返回0
 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 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求和+1
 int leftSize = leftInfo == null ? 0 : leftInfo.allSize;
 int rightSize = rightInfo == null ? 0 : rightInfo.allSize;
 //当前节点为二叉搜索树，那么最大二叉搜索子树就是自己，大小就是左右树大小求和+自身1
 p3 = 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;
 }
 ArrayList<Node> arr = getPrelist(head);
 HashMap<Node, 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 ArrayList<Node> getPrelist(Node head) {
 ArrayList<Node> arr = new ArrayList<>();
 fillPrelist(head, arr);
 return arr;
 }
 
 public static void fillPrelist(Node head, ArrayList<Node> arr) {
 if (head == null) {
 return;
 }
 arr.add(head);
 fillPrelist(head.left, arr);
 fillPrelist(head.right, arr);
 }
 
 public static HashMap<Node, Node> getParentMap(Node head) {
 HashMap<Node, Node> map = new HashMap<>();
 map.put(head, null);
 fillParentMap(head, map);
 return map;
 }
 
 public static void fillParentMap(Node head, HashMap<Node, 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(HashMap<Node, Node> parentMap, Node o1, Node o2) {
 HashSet<Node> 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){
 //空树，那么直接返回最大距离和高度都是0
 return 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：最大距离经过当前节点，取左树高度+右树高度+当前节点1
 int p3 = leftInfo.height + rightInfo.height + 1;
 return new Info(Math.max(p1, Math.max(p2,p3)),height);
 }
 
 // for test
 public static Node generateRandomBST(int maxLevel, int maxValue) {
 return generate(1, maxLevel, maxValue);
 }
 
 // for test
 public 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;
 }
 ArrayList<Node> 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, ArrayList<Node> 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：同步按 左右子树其一是最大二叉搜索树的两种情况进行赋值maxSubBSTHead
 if (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))) {
 //符合则刷新最大二叉搜索树节点和大小 大小就是左右树大小和+1
 maxSubBSTHead = head;
 maxSubBSTSize = (leftInfo == null ? 0 : leftInfo.maxSubBSTSize) + (rightInfo == null ? 0 : rightInfo.maxSubBSTSize) + 1;
 }
 return new Info(maxSubBSTHead,maxSubBSTSize,max,min);
 }
 
 // for test
 public static Node generateRandomBST(int maxLevel, int maxValue) {
 return generate(1, maxLevel, maxValue);
 }
 
 // for test
 public 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的最低公共祖先* 
> *\* * 
> *\* 分析情况：* 
> *\* 1.最低公共祖先不在head:* 
> *\* 在左树中找到a b 最低公共祖先，那么将该ans节点往上返回给头节点* 
> *\* 在右树找到，同理返回上层* 
> *\* 2.最低公共祖先在head:* 
> *\* 那么肯定 a b 分别都能在子树中找到* 
> *\* * 
> *\* 这里注意找 a b 节点除了在节点的子树找之外，也要判断当前节点是否为a b 可能递归到相等的时候* 
> *\*/*

package class13;
 
 import java.util.ArrayList;
 import java.util.HashMap;
 import java.util.HashSet;
 
 /**
 * 给定一棵二叉树的头节点head，和另外两个节点a和b。
 * 返回a和b的最低公共祖先
 * 
 * 分析情况：
 * 1.最低公共祖先不在head:
 * 在左树中找到a b 最低公共祖先，那么将该ans节点往上返回给头节点
 * 在右树找到，同理返回上层
 * 2.最低公共祖先在head:
 * 那么肯定 a b 分别都能在子树中找到
 * 
 * 这里注意找 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的父节点是value
 HashMap<Node, Node> parentMap = new HashMap<>();
 parentMap.put(head, null);
 fillParentMap(head, parentMap);
 HashSet<Node> 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, HashMap<Node, 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，也没有最低祖先null
 return 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 test
 public static Node generateRandomBST(int maxLevel, int maxValue) {
 return generate(1, maxLevel, maxValue);
 }
 
 // for test
 public 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 test
 public static Node pickRandomOne(Node head) {
 if (head == null) {
 return null;
 }
 ArrayList<Node> arr = new ArrayList<>();
 fillPrelist(head, arr);
 int randomIndex = (int) (Math.random() * arr.size());
 return arr.get(randomIndex);
 }
 
 // for test
 public static void fillPrelist(Node head, ArrayList<Node> 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; // 这名员工可以带来的快乐值 
> List<Employee> subordinates; // 这名员工有哪些直接下级 
> \} 
> 公司的每个员工都符合 Employee 类的描述。整个公司的人员结构可以看作是一棵标准的、没有环的多叉树。树的头节点是公司唯一的老板。除老板之外的每个员工都有唯一的直接上级。 叶节点是没有任何下属的基层员工(subordinates列表为空)，除基层员工外，每个员工都有一个或多个直接下级。 
> 这个公司现在要办party，你可以决定哪些员工来，哪些员工不来，规则： 
> 1.如果某个员工来了，那么这个员工的所有直接下级都不能来 
> 2.派对的整体快乐值是所有到场员工快乐值的累加 
> 3.你的目标是让派对的整体快乐值尽量大 
> 给定一棵多叉树的头节点boss，请返回派对的最大快乐值。 
> ***\* //分情况：*** 
> ***\* 1.当前节点来参加： 那么下层节点就都不能参加 快乐值0*** 
> ***\* 2.当前节点不来参加： 那么下层节点可参加，可不参加，取两者快乐值最大***

package class13;
 /**
 * 派对的最大快乐值
 *
 * 员工信息的定义如下:
 * class Employee {
 * public int happy; // 这名员工可以带来的快乐值
 * List<Employee> 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 List<Employee> 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){
 //空节点，也就是没有员工，那么更没有参加与否的快乐值 0
 return 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值，当前节点参加，那么子节点不能参加，快乐值0
 yes += nextInfo.no;
 }
 return new Info(no,yes);
 }
 
 // for test
 public 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 test
 public 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!");
 }
 
 }