package com.xiaodai.algorithm;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/**
* Author ：dai
* Date ：2020/12/25 2:56 下午
* Description：二叉树基本结构和算法
*/
public class TreeBaseUtil {
/**
* 二叉树节点定义
*/
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int v) {
this.value = v;
}
}
/**
* 递归先序遍历
*
* @param head
*/
public static void pre(Node head) {
if (head == null) {
return;
}
System.out.println(head.value);
pre(head.left);
pre(head.right);
}
/**
* 递归中序遍历
*
* @param head
*/
public static void mid(Node head) {
if (head == null) {
return;
}
mid(head.left);
System.out.println(head.value);
mid(head.right);
}
/**
* 递归后续遍历
*
* @param head
*/
public static void pos(Node head) {
if (head == null) {
return;
}
pos(head.left);
pos(head.right);
System.out.println(head.value);
}
/**
* 非递归先序
*
* @param head
*/
public static void NotRRre(Node head) {
System.out.print("pre-order: ");
if (head != null) {
// 借助栈结构，手动压栈
Stack<Node> stack = new Stack<>();
stack.add(head);
while (!stack.isEmpty()) {
// 弹出就打印
head = stack.pop();
System.out.println(head.value);
// 右孩子不为空，先压入右孩子。右孩子就会后弹出
if (head.right != null) {
stack.push(head.right);
}
// 左孩子不为空，压入左孩子，左孩子在右孩子之后压栈，先弹出
if (head.left != null) {
stack.push(head.left);
}
}
}
}
/**
* 非递归中序
*
* @param head
*/
public static void NotRMid(Node head) {
System.out.print("mid-order: ");
if (head != null) {
Stack<Node> stack = new Stack<>();
while (!stack.isEmpty() || head != null) {
// 整条左边界以此入栈
if (head != null) {
stack.push(head);
// head滑到自己的左孩子，左孩子有可能为空，但空的节点不会加入栈，下一个分支会判空处理
head = head.left;
// 左边界到头弹出一个打印，来到该节点右节点，再把该节点的左树以此进栈
} else {// head为空的情况，栈顶是上次头结点的现场，head等于栈顶，回到上一个现场。打印后，head往右树上滑动
head = stack.pop();
System.out.println(head.value);
head = head.right;
}
}
}
}
/**
* 非递归后序，借助两个栈，比借助一个栈容易理解
*
* @param head
*/
public static void NotRPos(Node head) {
System.out.print("pos-order: ");
if (head != null) {
Stack<Node> s1 = new Stack<>();
// 辅助栈
Stack<Node> s2 = new Stack<>();
s1.push(head);
while (!s1.isEmpty()) {
head = s1.pop();
s2.push(head);
if (head.left != null) {
s1.push(head.left);
}
if (head.right != null) {
s1.push(head.right);
}
}
while (!s2.isEmpty()) {
System.out.print(s2.pop().value + " ");
}
}
System.out.println();
}
/**
* 非递归后序,仅借助一个栈，比较有技巧
*
* @param head
*/
public static void NotRPos2(Node head) {
System.out.print("pos-order: ");
if (head != null) {
Stack<Node> stack = new Stack<>();
stack.push(head);
Node c = null;
while (!stack.isEmpty()) {
c = stack.peek();
if (c.left != null && head != c.left && head != c.right) {
stack.push(c.left);
} else if (c.right != null && head != c.right) {
stack.push(c.right);
} else {
System.out.print(stack.pop().value + " ");
head = c;
}
}
}
System.out.println();
}
/**
* 按层遍历，即宽度优先遍历
*
* @param head
*/
public static void level(Node head) {
if (head == null) {
return;
}
// 借助队列
Queue<Node> queue = new LinkedList<>();
queue.add(head);
while (!queue.isEmpty()) {
Node cur = queue.poll();
// 打印当前
System.out.println(cur.value);
// 当前节点有左孩子，加入左孩子进队列
if (cur.left != null) {
queue.add(cur.left);
}
// 当前节点有右孩子，加入右孩子进队列
if (cur.right != null) {
queue.add(cur.right);
}
}
}
/**
* 二叉树先序序列化；除了先序，中序，后续，按层都可，但是序列化和反序列化规则要对应
* @param head
* @return
*/
public static Queue<String> preSerial(Node head) {
Queue<String> ans = new LinkedList<>();
pres(head, ans);
return ans;
}
private static void pres(Node head, Queue<String> ans) {
if (head == null) {
ans.add(null);
} else {
ans.add(String.valueOf(head.value));
pres(head.left, ans);
pres(head.right, ans);
}
}
/**
* 根据先序序列化的结构，还原树
*
* @param prelist
* @return
*/
public static Node buildByPreQueue(Queue<String> prelist) {
if (prelist == null || prelist.size() == 0) {
return null;
}
return preb(prelist);
}
public static Node preb(Queue<String> prelist) {
String value = prelist.poll();
// 如果头节点是空的话，返回空
if (value == null) {
return null;
}
// 否则根据第一个值构建先序的头结点
Node head = new Node(Integer.valueOf(value));
// 递归建立左树
head.left = preb(prelist);
// 递归建立右树
head.right = preb(prelist);
return head;
}
}package com.xiaodai.algorithm;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
/**
* Author ：dai
* Date ：2020/12/30 2:56 下午
* Description：解决二叉树的具体问题，递归思维的建立
*/
public class TreeSolvingUtil {
/**
* 节点信息
*/
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
/**
* 1、判断二叉树是否是平衡的
*
* @param head
* @return
*/
public static boolean isBalanced(Node head) {
return isBalancedProcess(head).isBalanced;
}
/**
* 1. 递归调用，head传入整体需要返回一个信息
* 2. 解决当前节点的Info信息怎么得来
*
* @param head
* @return
*/
private static IsBalancedInfo isBalancedProcess(Node head) {
if (head == null) {
return new IsBalancedInfo(true, 0);
}
IsBalancedInfo leftInfo = isBalancedProcess(head.left);
IsBalancedInfo rightInfo = isBalancedProcess(head.right);
// 当前节点的高度，等于左右树最大的高度，加上当前节点高度1
int currentHeight = Math.max(leftInfo.height, rightInfo.height) + 1;
boolean isBalanced = true;
// 左树不平衡，或者右树不平衡，或者左右树高度差大于1
if (!leftInfo.isBalanced || !rightInfo.isBalanced || Math.abs(leftInfo.height - rightInfo.height) > 1) {
isBalanced = false;
}
return new IsBalancedInfo(isBalanced, currentHeight);
}
/**
* 递归过程中需要整合的信息体
*/
public static class IsBalancedInfo {
// 是否平衡
boolean isBalanced;
// 高度多少
int height;
IsBalancedInfo(boolean b, int height) {
this.isBalanced = b;
this.height = height;
}
}
/**
* 2、二叉树中，获取任意两个节点的最大距离
*
* @param head
* @return
*/
public static int maxDistance(Node head) {
return maxDistanceProcess(head).maxDistance;
}
/**
* 任意节点需要返回的信息体：以该节点为头的高度，整棵树的最大距离
*/
public static class MaxDistanceInfo {
public int maxDistance;
public int height;
public MaxDistanceInfo(int dis, int h) {
this.maxDistance = dis;
this.height = h;
}
}
private static MaxDistanceInfo maxDistanceProcess(Node head) {
if (head == null) {
return new MaxDistanceInfo(0, 0);
}
MaxDistanceInfo leftInfo = maxDistanceProcess(head.left);
MaxDistanceInfo rightInfo = maxDistanceProcess(head.right);
// 当前节点为头的情况下，高度等于左右树较大的高度，加上1
int height = Math.max(leftInfo.height, rightInfo.height) + 1;
// 当前节点为头的情况下，最大距离等于，左右树距离较大的那个距离(与当前节点无关的情况)
// 和左右树高度相加再加上当前节点距离1的距离(与当前节点有关的情况)取这两种情况较大的那个
int maxDistance = Math.max(Math.max(leftInfo.maxDistance, rightInfo.maxDistance)
, (leftInfo.height + rightInfo.height + 1));
return new MaxDistanceInfo(maxDistance, height);
}
/**
* 3、判断一颗树是否是满二叉树
*
* @param head
* @return
*/
public static boolean isFull(Node head) {
if (head == null) {
return true;
}
IsFullInfo all = isFullProcess(head);
// 递归拿到整棵树的头结点个数，根据满二叉树的公式，验证。（高度乘以2） - 1 = 节点个数
return (1 << all.height) - 1 == all.nodes;
}
/**
* 判断一棵树是否是满二叉树，每个节点需要返回的信息
*/
public static class IsFullInfo {
public int height;
public int nodes;
public IsFullInfo(int height, int nodes) {
this.height = height;
this.nodes = nodes;
}
}
private static IsFullInfo isFullProcess(Node head) {
// base 空节点的高度为0，节点数量也0
if(head == null) {
return new IsFullInfo(0,0);
}
// 左树信息
IsFullInfo leftInfo = isFullProcess(head.left);
// 右树信息
IsFullInfo rightInfo = isFullProcess(head.right);
// 当前节点为头的树，高度
int height = Math.max(leftInfo.height, rightInfo.height) + 1;
// 当前节点为头的树，节点数量
int nodes = leftInfo.nodes + rightInfo.nodes + 1;
return new IsFullInfo(height, nodes);
}
/**
* 4、找到二叉树中节点和等于sum的最长路径
* @param head
* @param sum
* @return
*/
public int getMaxLength(Node head, int sum) {
Map<Integer, Integer> sumMap = new HashMap<>();
sumMap.put(0, 0); // 重要
return preOrder(head, sum, 0, 1, 0, sumMap);
}
private int preOrder(Node head, int sum, int preSum, int level, int maxLen, Map<Integer, Integer> sumMap) {
if(head == null) {
return maxLen;
}
int curSum = preSum + head.value;
if(!sumMap.containsKey(curSum)) {
sumMap.put(curSum, level);
}
if(sumMap.containsKey(curSum - sum)) {
maxLen = Math.max(level - sumMap.get(curSum - sum), maxLen);
}
maxLen = preOrder(head.left, sum, curSum, level + 1, maxLen, sumMap);
maxLen = preOrder(head.right, sum, curSum, level + 1, maxLen, sumMap);
if(level == sumMap.get(curSum)) {
sumMap.remove(curSum);
}
return maxLen;
}
/**
* 5、二叉树按层打印
*
* last：表示正在打印的当前行的最右节点
* nLast：表示下一行的最右节点
*/
public void printByLevel(Node head) {
if(head == null) {
return;
}
Queue<Node> queue = new LinkedList<>();
int level = 1;
Node last = head;
Node nLast = null;
queue.offer(head);
System.out.println("Level " + (level++) + " : ");
while (!queue.isEmpty()) {
head = queue.poll();
System.out.println(head.value + " ");
if(head.left != null) {
queue.offer(head.left);
nLast = head.left;
}
if(head.right != null) {
queue.offer(head.right);
nLast = head.right;
}
if(head == last && !queue.isEmpty()) {
System.out.println("\nLevel " + (level++) + " ");
last = nLast;
}
}
System.out.println();
}
/**
* 6、二叉树zigzag打印
*/
/**
* 7、二叉树，给定量给节点，求这两个节点的最近公共祖先
*/
}