由二叉树到贪心算法

public static class Node{
public int value;
public Node left;
public Node right;


public Node(int v){
value =v;
}
}
遍历模板
public static void f(Node head){
if (head == null){
return;
}
1
f(head.left);
2
f(head.right);
3
}

//前序遍历 根--》左--》右
public static void pre(Node head){
if (head == null){
return;
}
System.out.println(head.value);
pre(head.left);
pre(head.right);
}

//前序遍历 根--》左--》右
public static void pre(Node head){
if (head == null){
return;
}
System.out.println(head.value);
pre(head.left);
pre(head.right);
}

后序遍历 左--》右--》根
public static void pos(Node head){
if (head == null){
return;
}
pos(head.left);
pos(head.right);
System.out.println(head.value);
}

//前序遍历 根--》左--》右
public static void unRecursivePre(Node head){
if (head!=null){
Stack stack = new Stack<>();
stack.add(head);
while (!stack.isEmpty()){
head = stack.pop();
System.out.println(head.value);
if (head.left!=null){
stack.add(head.left);
}
if (head.right!=null){
stack.add(head.right);
}
}
}
}

//前序遍历 左--》根--》右
public static void unRecursiveIn(Node head){
if (head!=null){
Stack stack = new Stack<>();
stack.add(head);
while (!stack.isEmpty() || head!=null){
if (head!=null){
stack.push(head);
head = head.left;
}else {
head = stack.pop();
System.out.println(head.value);
head = head.right;
}
}
}
}

//左--》右--》根
public static void unRecursivePos(Node head){
if (head!=null){
Stack s1 = new Stack<>();
Stack 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.println(s2.pop());
}
}
}

public static void level(Node head){
if (head == null){
return;
}
Queue 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);
}
}
}

public static class Node{
public int value;
public Node left;
public Node right;


public Node(int v){
value =v;
}
}


public static Queue fSerial(Node head){
Queue ans = new LinkedList<>();
fpres(head,ans);
return ans;
}


public static void fpres(Node head,Queue ans){
if (head == null){
ans.add(null);
}else {
1
ans.add(String.valueOf(head.value));
2
fpres(head.left,ans);
3
fpres(head.right,ans);
}
}

public static class Node {
public int value;
public Node left;
public Node right;


public Node(int v) {
value = v;
}
}


public static int maxWidthUseMap(Node head) {
if (head == null) {
return 0;
}
Queue queue = new LinkedList<>();
queue.add(head);
key 在哪一层 value
HashMap levelMap = new HashMap<>();
levelMap.put(head, 1);
int curLevel = 1;//当前正在统计的层
int curLevelNodes = 0; 当前层的宽度是多少。
int max = 0;
while (!queue.isEmpty()) {
Node cur = queue.poll();
int curNodeLevel = levelMap.get(cur);
if (cur.left != null) {
levelMap.put(cur.left, curNodeLevel + 1);
queue.add(cur.left);
}
if (cur.right != null) {
levelMap.put(cur.right, curNodeLevel + 1);
queue.add(cur.right);
}
if (curLevelNodes == curLevel) {
curLevelNodes++;
} else {
max = Math.max(max, curLevelNodes);
curLevel++;
curLevelNodes = 1;
}
}
max = Math.max(max, curLevelNodes);
return max;
}


public static int maxWidthNoMap(Node head) {
if (head == null) {
return 0;
}
Queue queue = new LinkedList<>();
queue.add(head);
Node curEnd = head;//当前层，最右节点是谁
Node nextEend = null;//下一层，最右侧节点是谁
int max = 0;
int curLevelNodes = 0;//当前节点数
while (!queue.isEmpty()) {
Node cur = queue.poll();
if (cur.right != null) {
queue.add(cur.right);
nextEend = cur.left;
}
if (cur.left != null) {
queue.add(cur.left);
nextEend = cur.left;
}
curLevelNodes++;
if (cur == curEnd){
max = Math.max(max,curLevelNodes);
curLevelNodes =0; 当前节点清0
curEnd = nextEend;
}
}
return max;
}

public static void printAllFolds(int N) {
先从头结点出发，i初始值为1，切第一次的头结点折痕为凹折痕
printProcess(1, N, true);
}


递归过程，来到了某一个节点，
i是节点的层数，N一共的层数，down == true 凹 down == 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);
}


public static void main(String[] args) {
int N = 3;
printAllFolds(N);
}

public static class Node {
public int value;
public Node left;
public Node right;


public Node(int data) {
this.value = data;
}
}


//节点的可以得到的信息
public static class Info {
boolean isBST;
public int min;
public int max;


public Info(boolean is, int mi, int ma) {
isBST = is;
min = mi;
max = ma;
}
}


//开始组装节点返回信息 （重要）
public static Info process(Node head) {
if (head == null) {
return null;
}
Info leftInfo = process(head.left);
Info rightInfo = process(head.right);
int min = head.value;
int max = head.value;
if (leftInfo != null) {
min = Math.min(min, leftInfo.min);
max = Math.max(max, leftInfo.max);
}
if (rightInfo != null) {
min = Math.min(min, rightInfo.min);
max = Math.max(max, rightInfo.max);
}
//设置可能性
boolean isBST = false;
if (
(leftInfo == null ? true : (leftInfo.isBST && leftInfo.max
&&
(rightInfo == null ? true : (rightInfo.isBST && rightInfo.min > head.value))
) {
isBST = true;
}
return new Info(isBST, min, max);
}


public static boolean isBST(Node head) {
if (head == null) {
return true;
}
return process(head).isBST;
}

public static boolean isBalanced(Node head) {
return process(head).isBalaced;
}


// 左、右要求一样，Info 信息返回的结构体
public static class Info {
public boolean isBalaced;
public int height;


public Info(boolean b, int h) {
isBalaced = b;
height = h;
}
}


public static Info process(Node X) {
if (X == null) {
return new Info(true, 0);
}
Info leftInfo = process(X.left);
Info rightInfo = process(X.right);
int height = Math.max(leftInfo.height, rightInfo.height) + 1;
boolean isBalanced = true;
// 设置不是的情况
if (!leftInfo.isBalaced || !rightInfo.isBalaced || Math.abs(leftInfo.height - rightInfo.height) > 1) {
isBalanced = false;
}
return new Info(isBalanced, height);
}

void sort(int[] nums, int lo, int hi) {
/****** 前序遍历位置 ******/
// 通过交换元素构建分界点 p
int p = partition(nums, lo, hi);
/************************/


sort(nums, lo, p - 1);
sort(nums, p + 1, hi);
}





void sort(int[] nums, int lo, int hi) {
int mid = (lo + hi) / 2;
sort(nums, lo, mid);
sort(nums, mid + 1, hi);


/****** 后序遍历位置 ******/
// 合并两个排好序的子数组
merge(nums, lo, mid, hi);
/************************/
}

public static int lessMoney(int[] arr) {
PriorityQueue pQ = new PriorityQueue<>();
for (int i = 0; i
pQ.add(arr[i]);
}
int sum = 0;
int cur = 0;
while (pQ.size() > 1) {
cur = pQ.poll() + pQ.poll();
sum += cur;
pQ.add(cur);
}
return sum;
}