zcy 二叉树 6-7
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main{
public static void main(String args[]) {
Node head = new Node(1);
head.left = new Node(2);
head.right = new Node(3);
head.left.left = new Node(4);
head.left.right = new Node(5);
head.right.left = new Node(6);
head.right.right = new Node(7);
// recursive
System.out.println("==========recursive==========");
System.out.print("pre-order: ");
preOrderRecur(head);
System.out.println();
System.out.print("in-order: ");
inOrderRecur(head);
System.out.println();
System.out.print("pos-order: ");
posOrderRecur(head);
System.out.println();
// unrecursive
System.out.println("==========unrecursive==========");
preOrderUnRecur(head);
inOrderUnRecur(head);
posOrderUnRecur1(head);
// posOrderUnRecur2(head);
System.out.println("该二叉树的最大宽度为 " + maxWidth(head));
System.out.println("该二叉树的最大宽度为 " + maxWidth2(head));
}
public static class Node {
public int val;
public Node left;
public Node right;
public Node(int val) {
this.val = val;
}
}
public static void preOrderRecur(Node head) {
if(head == null) {
return;
}
System.out.print(head.val + " ");
preOrderRecur(head.left);
preOrderRecur(head.right);
}
public static void inOrderRecur(Node head) {
if(head == null) {
return;
}
inOrderRecur(head.left);
System.out.print(head.val + " ");
inOrderRecur(head.right);
}
public static void posOrderRecur(Node head) {
if(head == null) {
return;
}
posOrderRecur(head.left);
posOrderRecur(head.right);
System.out.print(head.val + " ");
}
public static void preOrderUnRecur(Node head) {
System.out.print("pre-order: ");
if(head != null) {
Stack<Node> stack = new Stack<Node>();
stack.add(head);
while(!stack.isEmpty()) {
Node cur = stack.pop();
System.out.print(cur.val + " ");
if(cur.right != null) {
stack.push(cur.right);
}
if(cur.left != null) {
stack.push(cur.left);
}
}
}
System.out.println();
}
public static void posOrderUnRecur1(Node head) {
System.out.print("pos-order: ");
if(head != null) {
Stack<Node> s1 = new Stack<Node>();
Stack<Node> s2 = new Stack<Node>();
s1.add(head);
while(!s1.isEmpty()) {
Node cur = s1.pop();
s2.push(cur);
if(cur.left != null) {
s1.push(cur.left);
}
if(cur.right != null) {
s1.push(cur.right);
}
}
while(!s2.isEmpty()) {
System.out.print(s2.pop().val + " ");
}
}
System.out.println();
}
public static void inOrderUnRecur(Node head) {
System.out.print("in-order: ");
Stack<Node> stack = new Stack<Node>();
Node cur = head;
//cur来到一个节点，只要有左边界，全部压栈，然后依次弹出节点，如果弹出节点有右子树，cur来到右子树的根节点把左边界全部压栈，
//如果弹出节点没有右子树就继续弹出节点
//会发现该流程中只有把子树的左边界压栈，原理：整棵树能被左边界分解
while(!stack.isEmpty() || cur != null) {
//把以cur为根的子树的左边界进栈，直到cur == null了然后开始弹节点
if(cur != null) { //刚开始把整棵树的左边界压栈 或者 弹出节点的右子树不为空，要把右子树的左边界压栈时进入if，把左边界全都压栈
stack.push(cur);
cur = cur.left;
} else { //左边界全都压栈了 或者 弹出节点的右子树为空时，此时cur == null，进入else，继续弹出节点
cur = stack.pop();
System.out.print(cur.val + " ");
cur = cur.right;
}
}
System.out.println();
}
public static void w(Node head) {
if(head == null) {
return;
}
Queue<Node> queue = new LinkedList<Node>();
queue.add(head);
while(!queue.isEmpty()) {
Node cur = queue.poll();
System.out.print(cur.val + " ");
if(cur.left != null) {
queue.offer(cur.left);
}
if(cur.right != null) {
queue.offer(cur.right);
}
}
System.out.println();
}
//返回二叉树的最大宽度
public static int maxWidth(Node head) {
Queue<Node> queue = new LinkedList<Node>();
queue.offer(head);
HashMap<Node, Integer> levelMap = new HashMap<>(); //levelMap表记录每个节点所在层数
levelMap.put(head, 1);
int curLevel = 1; //当前所在层，即要统计宽度的那一层，或者叫当前待统计层
int max = 1; //最大宽度
int curLevelNodes = 0; //当前待统计层已经发现的节点数
while(!queue.isEmpty()) {
Node cur = queue.poll();
//当前遍历到的节点所在的层数，根据curNodeLevel来判断现在是继续统计该层，还是该结算了，即当前待统计层是否统计完了
int curNodeLevel = levelMap.get(cur);
//如果当前遍历到的节点所在的层数==当前待统计的层数
if(curNodeLevel == curLevel) {
curLevelNodes++;
} else { //如果不等于，一定是当前遍历到的节点已经是当前待统计层的下一层了，即当前待统计层已经统计完宽度了，该结算了
max = Math.max(max, curLevelNodes);
curLevel++;
curLevelNodes = 1;
}
if(cur.left != null) {
//每个进入队列的节点在二叉树中的层数都需要记录到levelMap表中
//这样之后弹出该节点时，才能知道该节点的层数
levelMap.put(cur.left, curLevel + 1);
queue.offer(cur.left);
}
if(cur.right != null) {
levelMap.put(cur.right, curLevel + 1);
queue.offer(cur.right);
}
}
//注意！！当统计完最后一层的最后一个节点，队列就空了，会退出while循环，所以要在while循环外单独结算最后一层的max
max = Math.max(max, curLevelNodes);
return max;
}
//返回二叉树的最大宽度，不使用哈希表的代码
public static int maxWidth2(Node head) {
Queue<Node> queue = new LinkedList<Node>();
queue.offer(head);
Node curLevelEnd = head; //当前待统计层的最后一个节点 或 当前遍历节点所在层中的最后一个节点是谁
//当前待统计层的下一层的最后一个节点 或 当前遍历节点所在层的下一层的最后一个节点是谁
//只有当遍历到当前待统计层的最后一个节点，并根据它是否存在左右孩子节点做完相应操作后，
//此时nextLevelEnd才真正指向当前待统计层的下一层的最后一个节点
Node nextLevelEnd = null;
int curLevelNodes = 0; ////当前待统计层已经发现的节点数
int max = 1;
while(!queue.isEmpty()) {
Node cur = queue.poll();
curLevelNodes++; //在待统计层发现了一个节点
if(cur.left != null) {
queue.offer(cur.left);
nextLevelEnd = cur.left; //把当前在待统计层遍历到的节点的左孩子节点设为下一层的最后一个节点
}
if(cur.right != null) {
queue.offer(cur.right);
nextLevelEnd = cur.right;
}
//判断当前在待统计层遍历到的节点是不是当前待统计层的最后一个节点，如果不是，继续遍历下一个当前待统计层的节点
//如果是，说明当前待统计层已经统计完了，接下来遍历到的节点都是下一层的了，要统计下一层了，所以结算max，
//把curLevelNodes清零，设置接下来要统计的那层的最后一个节点是谁
//简言之，通过下面这个if判断，我们能发现当前层什么时候结束，下一层什么时候开始
if(cur == curLevelEnd) {
max = Math.max(max, curLevelNodes);
curLevelNodes = 0;
//在开始要统计新的一层的宽度时，该层的最后一个节点是谁就已经知道了，
//算是这个算法的核心基础、要点，正是在这个基础上，我们才能正确地结算，或者是继续统计当前层
//即我们才能正确地发现当前层什么时候结束，下一层什么时候开始
curLevelEnd = nextLevelEnd;
nextLevelEnd = null;
}
}
return max;
}
public static int preValue = Integer.MIN_VALUE;
public static boolean isBstRecur(Node head) {
if(head == null) {
return true;
}
boolean isLeftBST = isBstRecur(head.left);
if(!isLeftBST) {
return false;
}
if(head.val <= preValue) {
return false;
} else {
preValue = head.val;
}
return isBstRecur(head.right);
}
public static boolean isBstUnRecur(Node head) {
Stack<Node> stack = new Stack<>();
Node cur = head;
int preValue = Integer.MIN_VALUE;
while(!stack.isEmpty() || cur != null) {
if(cur != null) {
stack.push(cur);
cur = cur.left;
} else {
cur = stack.pop();
if(cur.val <= preValue) {
return false;
} else {
preValue = cur.val;
}
cur = cur.right;
}
}
return true;
}
//判断是否为完全二叉树
//流程：按宽度遍历，依次遍历每个节点的过程中，如果出现了第一种情况，（1）遇到的节点有右孩子，但没左孩子，直接返回false，
//因为这能说明它不是从左往右依次变满的，在第一个条件不违规的情况下，如果遇到了第一个左右孩子不双全的情况（其实就是有左无右，
//或者左右都无），那么接下来遇到的所有节点，都必须是叶子节点
public static boolean isCbt(Node head) {
if(head == null) {
return true;
}
Queue<Node> queue = new LinkedList<>();
queue.offer(head);
//leaf表示一个开关，且只有开没有关，表示事件“是否遇到过左右两个孩子不双全的节点”是否发生，发生了就将开关打开(true)
boolean leaf = false;
Node l = null;
Node r = null;
while(!queue.isEmpty()) {
Node cur = queue.poll();
l = cur.left;
r = cur.right;
//如果 有右无左 || 已经遇到了左右孩子不双全的节点之后，又遇到了非叶子节点 (l != null || r != null)
if( (l == null && r != null) || (leaf && (l != null || r != null))) {
return false;
}
//遇到了左右孩子不双全的节点（具体点就是有左无右，或者左右都无，只不过这样的条件判断表达式会更复杂，
//所以就按左右孩子不双全来判断就行，反正结果也是正确的）
if(l == null || r == null) {
leaf = true;
}
if(l != null) {
queue.offer(l);
}
if(r != null) {
queue.offer(r);
}
}
return true;
}
public static boolean isBalance(Node head) {
return isBalanceRecur(head).isBalance;
}
public static class AvlMesStruc {
public boolean isBalance;
public int height;
public AvlMesStruc(boolean isB, int hei) {
this.isBalance = isB;
this.height = hei;
}
}
//返回以head为根的子树的信息结构（包含两个信息：是否为AVL，高度为多少）
public static MessageStruc isBalanceRecur(Node head) {
if(head == null) {
return new AvlMesStruc(true, 0);
}
AvlMesStruc leftMessage = isBalanceRecur(head.left);
AvlMesStruc rightMessage = isBalanceRecur(head.right);
int height = Math.max(leftMessage.height, rightMessage.height) + 1;
boolean isBalance = leftMessage.isBalance && rightMessage.isBalance && Math.abs(leftMessage.height - rightMessage.height) <= 1;
return new AvlMesStruc(isBalance, height);
}
public static boolean isBST(Ndoe head) {
return isBST_Recur(head).isBST;
}
public static class BstMesStruc {
public boolean isBST;
public int max;
public int min;
public BstMesStruc(boolean isBST, int max, int min) {
this.isBst = isBST;
this.max = max;
this.min = min;
}
}
public static BstMesStruc isBST_Recur(Node head) {
if(head == null) {
return null; //如果base case是返回空，那么下面调用leftMes, rightMes的时候就要做判断了,否则会报空指针异常 7、图 51:10-51:41
}
BstMesStruc leftMes = isBST_Recur(head.left);
BstMesStruc rightMes = isBST_Recur(head.right);
//该子树的min为左子树的min、右子树的min、根节点head.val中的最小值，max同理
int min = head.val;
int max = head.val;
if(leftMes != null) {
min = Math.min(min, leftMes.min);
max = Math.max(max, leftMes.max);
}
if(rightMes != null) {
min = Math.min(min, rightMes.min);
max = Math.max(max, rightMes.max);
}
//四个条件 左子树为BST 右子树为BST 左子树max < head.val 右子树min > head.val 都为真，isBST才为真，四个条件是&&的关系
//所以反过来看，只要上述四个条件中的一个为假，isBST就为假
boolean isBST = true;
if(leftMes != null && (!leftMes.isBST || leftMes.max >= head.val)) {
isBST = false;
}
if(rightMes != null && (!rightMes,isBST || rightMes.min <= head.val)) {
isBST = false;
}
// boolean isBST;
// if(leftMes == null && rightMes == null) {
// isBST = true;
// } else if(leftMes != null && rightMes == null) {
// isBST = leftMes.isBST && leftMes.max < head.val;
// } else if( leftMes == null && rightMes != null) {
// isBST = rightMes.isBST && rightMes.min > head.val;
// } else {
// isBST = leftMes.isBST && leftMes.max < head.val && rightMes.isBST && rightMes.min > head.val;
// }
boolean isBST = false;
if( (leftMes != null ? (leftMes.isBST && leftMes.max < head.val) : true)
&&
(rightMes != null ? (rightMes.isBST && rightMes.min > head.val) : true) ) {
isBST = true;
}
return new BstMesStruc(isBST, max, min);
}
//我自己写的
public static BstMesStruc isBST_Recur2(Node head) {
if(head == null) {
//把空树的max设成系统最小，这样后面在求含有空子树的子树的max时，空子树的max就不会带来影响,把min设为系统最大同理
return new BstMesStruc(true, Integer.MIN_VALUE, IntegerMAX_VALUE);
}
BstMesStruc leftMes = isBST_Recur2(head.left);
BstMesStruc rightMes = isBST_Recur2(head.right);
int max = Math.max(head.val, Math.max(leftMes.max, rightMes.max));
int min = Msth,min(head.val, Math.min(leftMes.min, rightMes.min));
boolean isBST = leftMes.isBST && leftMes.max < head.val && rightMes.isBST && rightMes.min > head.val;
return new BstMesStruc(isBST, max, min);
}
//判断是否是满二叉树
//公式 节点数 == 2的层数次幂 - 1
public static boolean isFull(Node head) {
if(head == null) {
return true;
}
Info data = isFullRecur(head);
return data.nodes == (1 << data.height - 1);
}
public static class Info {
public int height;
public int nodes;
public Info(int height, int nodes) {
this.height = height;
this.nodes = nodes;
}
}
public static Info isFullRecur(Node head) {
if(head == null) {
return new Info(0, 0);
}
Info leftData = isFullRecur(head.left);
Info rightData = isFullRecur(head.right);
int height = Math.max(leftData.height, rightData.height) + 1;
int nodes = leftData.nodes + rightData.nodes + 1;
return new Info(height, nodes);
}
//最低公共祖先问题
//前提：o1和o2一定属于以head为根的树
//流程：先把所有节点能够往上回溯这个机制搞好，即fatherMap生成好，然后o1往上窜的整条链放到set里去，然后再让o2往上窜，o2每窜一步，
//都检查他这个节点在不在o1的链里，直到第一次检查到在o1链里的节点，就是它们最初汇聚的点，即最低公共祖先
public static Node lowestCommonAncester(Node head, Node o1, Node o2) {
HashMap<Node, Node> fatherMap = new HashMap<>(); //记录以head为根的树上除了head外其他所有节点与对应父节点的表
creFatherMap(head, fatherMap);
// fatherMap.put(head, head);
HashSet<Node> set1 = new HashSet<>(); //记录沿o1往上的链经过的所有节点（包括o1自己），但不包括head
Node cur = o1;
while(cur != head) {
set1.add(cur);
cur = fatherMap.get(cur);
}
cur = o2;
while(cur != head) { //当cur == head而退出while循环，那么o1和o2的最低公共祖先就是head
if(set1.contains(cur)) {
break;
}
cur = fatherMap.get(cur);
}
return cur;
}
//通过递归遍历，设置好fatherMap表，这样每个节点就能往上回溯了
//只有head节点的fatherMap没有设置，即head没有父节点
public static void creFatherMap(Node head, HashMap<Node, Node> fatherMap) {
if(head == null) {
return;
}
fatherMap.put(head.left, head);
fatherMap.put(head.right, head);
//设置左树上所有节点的fatherMap
creFatherMap(head.left, fatherMap);
creFatherMao(head.right, fatherMap);
}
//最低公共祖先递归版本
//p和q的位置关系分为两种情况：(1)p和q不互为公共祖先，它们的lca是沿p往上的链和沿q往上的链第一次汇聚的那个点，
//所以，一个在lca的左树，另一个在lca的右树；(2)p和q互为公共祖先，不妨假设，p在q上面，那么p就是它们的lca
//lcaRecur函数的功能 或者说 lcaRecur函数返回值代表的意义：如果p和q都属于当前这个以head为根的子树，就返回它们的lca；如果p
//属于，q不属于，就返回p；如果p和q都不属于，就返回null
//每个节点最多会被遍历一次，所以最坏时间复杂度是O(n)
public static Node lcaRecur(Node head, Node p, Node q) {
if(head == null || head == p || head == q) {
return head;
}
//遍历到的每个点，都先去左树上搜一下有没有lca 或者p 或者q，有的话就返回回来，再去右树上搜一下有没有lca 或者p 或者q，
//然后根据两个返回值的不同情况，来决定往上返回啥
Node left = lcaRecur(head.left, p, q);
Node right = lcaRecur(head.right, p, q);
//是以后序遍历的顺序向上返回，如果p和q的位置关系是(1)情况，那么它们的lca调用lcaRecur得到两个返回值就应该分别是p和q，
//都不为空，然后就返回当前的head，即p和q的lca，之后遍历到的其他的子树上都没有p和q，所以返回的都是null，
//lca会被一直往上返回，结果正确；如果p和q的位置关系是(2)情况，不妨假设p在q上面，那么p就是它们的lca，
//那么遍历到p就会返回p，之后遍历到的其他的子树上都么有p和q，所以返回的都是null，p会被一直往上返回，结果也正确
//如果p和q的位置关系是第一种，那么这个if判断永远为false
//如果p和q的位置关系是第二种，那么只有遍历到它们的lca的时候，这个if判断才会为true，然后返回当前的head，即lca
if(left != null && right != null) {
return head;
}
if(left != null) {
return left;
}
return right;
// return left != null ? left : right;
}
//求节点x的后继节点（优化版本：如果x到它的后继节点y的距离是k，优化后的时间复杂度为O(k)）
//最直接的思路：先把中序遍历得到的序列放到list中，然后在这个list中找到节点x它的下一个节点，就是它的后继，
//代价是遍历所有的节点，得到一个list，才能直到任何一个节点的后继是谁，所以时间复杂度是O(n)
//假设x到它的后继节点y的距离是k，如果要求把时间复杂度优化到O(k)，那么我们就要搞清楚节点x的后继节点怎么在结构上找
public static Node getSuccessorNode(Node x) {
//如果x有右树，那么它的后继就是右树上的最左节点
if(x.right != null) {
x = x.right;
while(x.left != null) {
x = x.left;
}
return x;
}
//如果x没有右树，那么存在一个最小子树，x是这个子树的最右节点，且这个子树是某个节点的左树，则这个节点就是x的后继（因为
//中序遍历中，一个节点的左树上最右那个节点被遍历后，就轮到根节点），所以我们就从x开始一路往上找，
//当我发现某一个节点它是它父亲左孩子的时候，那个父就是x的后继；
//如果不存在这么个子树，则说明x是整棵树的最右节点，没有后继，对应从x一路往上找，都找不到一个节点是它父的左孩子，直到找到head，
//发现head的父亲为null，然后退出while
else {
Node parent = x.parent;
//有两种情况会退出while：(1)parent == null，即x是整棵树的最右节点；(2)parent.right != x，当前节点是它父的左孩子
while(parent != null && parent.right == x) {
x = parent;
parent = x.parent;
}
return parent;
}
}
//把以head为根的树序列化成字符串返回
public static String serialByPre(Node head) {
if(head == null) {
return "#_";
}
String res = head.val + "_";
res += serialByPre(head.left);
res += serialByPre(head.right);
return res;
}
public static Node deSerialByPreString(String preStr) {
String[] values = preStr.split("_");
Queue<String> queue = new LinkedList<>();
for(int i = 0; i < values.length; i++) {
queue.offer(values[i]);
}
return deSerialByPreOrder(queue);
}
//消耗队列去建整棵树，把根节点返回
public static Node deSerialByPreOrder(Queue<String> queue) {
String value = queue.poll();
if(value.equals("#")) {
return null;
}
//先建根节点，再建左子树，再建右子树
Node head = new Node(Integer.valueOf(value));
head.left = deSerialByOrder(queue);
head.right = deSerialByOreder(queue);
return head;
}
//折纸问题
//i表示当前来到了哪一层，N表示折叠几次->深度，down为true时表示凹，false->凸
//这个递归过程模拟了以中序遍历顺序打印一颗在内存不存在，只在你脑海中存在的一颗头节点为凹，
//每一颗左子树的根节点都为凹，每一颗右子树的根节点都为凸的二叉树的过程
public static void printProcess(int i, int N, boolean down) {
if(i > N) {
return;
}
printProcess(i + 1, N, true);
System.out.println(down ? "凹" : "凸");
printProcess(i + 1, N, false);
}
}
