二叉树
二叉树基本结构
class Node<V>{
V value;
Node left;
Node right;
}
遍历
递归遍历
先序遍历(头左右)
第一次到这个节点就打印
中序遍历(左头右)
第二次到自己才打印
后序遍历(左右头)
第三次到自己才打印
class Node{
public int value;
public Node left;
public Node right;
public Node(int data){
value = data;
}
}
public static void preOrder(Node head){
if(head == null){
return;
}
System.out.println(head.value+" ");
preOrder(head.left);
preOrder(head.right);
}
public static void midOrder(Node head){
if(head == null){
return;
}
midOrder(head.left);
System.out.println(head.value+" ");
midOrder(head.right);
}
public static void posOrder(Node head){
if(head == null){
return;
}
posOrder(head.left);
posOrder(head.right);
System.out.println(head.value+" ");
}
非递归遍历
先序
- 从栈中弹出一个节点cur
- 打印（处理）cur
- 先右再左（如果有）
- 从1开始循环
public static void preOrder(Node head){
Stack<Node> st = new Stack<>();
st.push(head);
while(!st.isEmpty()){
head = st.pop();
System.out.println(head.value);
if (head.right != null){ st.push(head.right); }
if (head.left != null){ st.push(head.left); }
}
}
中序
每颗子树整棵树左边界进栈，依次弹的过程中，打印，对弹出节点的右树循环该过程（左边界进栈..........）
原理：将整个树由左边界分解（同理可以右边界）
public static void midOrder(Node head){
if(head != null){
Stack<Node> st = new Stack<>();
while (!st.isEmpty() || head != null){
if (head != null){
st.push(head);
head = head.left;
}else{
head = st.pop();
System.out.println(head.value);
head = head.right;
}
}
}
}
//下面的是我的思路
public static void midOrder(Node head){
Stack<Node> st = new Stack<>();
st.push(head);
head = head.left;
while( !st.isEmpty() || head != null){
while (head != null){
st.push(head);
head = head.left;
}
head = st.pop();
System.out.println(head.value);
head = head.right;
}
}
后序
首先来看
中序-改：头右左压栈，为了实现后序，使用一个收集栈来接受压入栈弹出的节点
- 弹出cur节点进入收集栈
- cur放入收集栈
- cur分支先左再右入栈
- 从头开始循环
public static void posOrder(Node head){
Stack<Node> st1 = new Stack<>();
Stack<Node> st2 = new Stack<>();
st1.push(head);
while ( !st1.isEmpty() ) {
head = st1.pop();
st2.push(head);
if (head.left != null){ st1.push(head.left); }
if (head.right != null){ st1.push(head.right); }
}
while ( !st2.isEmpty() ){
System.out.println(st2.pop().value);
}
}
最后当节点全部进入收集栈，输出收集栈即可。==关键点：进入收集栈顺序为头右左，故输出顺序为左右头，完成后序。==
宽度优先遍历
用队列实现
public static void wide(Node head){
if (head == null) return;
Queue<Node> queue = new ArrayDeque<>();
queue.add(head);
while (!queue.isEmpty()){
Node cur = queue.poll();
System.out.print(cur.value+" ");
if (cur.left != null){
queue.add(cur.left);
}
if (cur.right != null){
queue.add(cur.right);
}
}
}
求最大宽度
使用哈希表
public static int wide(Node head){
if (head == null) return -1;
Queue<Node> queue = new ArrayDeque<>();
queue.add(head);
HashMap<Node,Integer> levelMap = new HashMap<>();
levelMap.put(head,1);
int curLevel = 1;
int curLevelNum = 0;
int max = -1;
while (!queue.isEmpty()){
Node cur = queue.poll();
int curNodeLevel = levelMap.get(cur);
if(curNodeLevel == curLevel){
curLevelNum++;
}else{
max = Math.max(max,curLevelNum);
curLevel++;
curLevelNum = 1;
}
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);
}
}
return max;
}
不用哈希表
- 永远让nextend指向最后进栈的
- 每一层到达最后一个节点，让curend指向nextend，nextend变成null
public static int wide(Node head){
Node curend=head;
Node nextend=null;
int curlevel=0,max=0;
Queue<Node> queue = new ArrayDeque<>();
queue.add(head);
while(head != null || !queue.isEmpty()){
if (queue.isEmpty()) return max;
head = queue.poll();
curlevel++;
if (head.left != null){
queue.add(head.left);
nextend = head.left;
}
if (head.right != null){
queue.add(head.right);
nextend = head.right;
}
if (head == curend ){
curend = nextend;
nextend = null;
max = Math.max(max,curlevel);
curlevel = 0;
}
}
return max;
}
搜索二叉树判断
左树小，中间，右树为大小顺序严格递增
可以联想到利用中序遍历，为一递增的顺序
普通版本
public static int prevalue = Integer.MIN_VALUE;
public static boolean checkBST(Node head){
if(head == null){
return;
}
boolean isleft = checkBST(head.left);
if(!isleft){
return false;
}
if(head.value <= prevalue){
return false;
}else{
prevalue = head.value
}
return checkBST(head.right);
}
傻白甜版本
public static void process2(Node head,List<Node> list){
if(head == null){
return false;
}
process2(head.left,list);
list.add(head);
process2(head.right,list);
}
public static boolean checkBST(Node head){
List<Node> list = new ArrayList<>();
process2(head,list);
//最后使用for()遍历集合判断大小即可
}
非递归版本
public static void midOrder(Node head){
if(head != null){
int prevalue = Integer.MIN_VALUE;
Stack<Node> st = new Stack<>();
while (!st.isEmpty() || head != null){
if (head != null){
st.push(head);
head = head.left;
}else{
head = st.pop();
if(head.value <= prevalue){
return false;
} else {
prevalue = head .value;
}
head = head.right;
}
}
}
}
完全二叉树
- 有右孩子无左孩子则返回false
- 满足1的前提下，如果遇到第一个左右不双全的情况，后续节点必须全部是叶节点
public static boolean isCST(Node head){
if(head == null){
return true;
}
Linkedlist<Node> queue = new Linkedlist<Node>();
//是否遇到左右两孩子不双全的情况
boolean leaf = false;
Node l = null;
Node r = null;
queue.add(head);
while( !queue.isEmpty()){
head = queue.poll();
l = head.left;
r = head.right;
//针对两个条件
if(
//遇到不双全的节点之后，又发现当前节点不是叶节点
(leaf &&(l != null || r != null))
||
//有右无左
(l == null && r!=null)
){
return false;
}
if(l!=null){
queue.add(l);
}
if(r!=null){
queue.add(r);
}
if(l==null || r==null){
leaf = true;
}
}
}
满二叉树
节点数 N = 2的l次方 - 1，l为最大深度,即每一层节点都是满的
满足上述公式即为满二叉树
套路-树型DP
套路平衡二叉树
public static class ReturnType{
public boolean isBalanced;
public int height;
public ReturnType(boolean isB,int heigh ){
isBalanced = isB;
height = heigh;
}
}
public static boolean isBalance(Node head){
return process(head).isBalanced;
}
public static ReturnType process(Node head){
if(head == null){
return new ReturnType(true,0);
}
ReturnType left = process(head.left);
ReturnType right = process(head.left);
int height = Math.max(left.height,right.height) + 1;
boolean isB = left.isBalanced && right.isBalanced
&& Math.abs(left.height - right.height) <2;
return new ReturnType(isB, height);
}
套路搜索二叉树
class ReturnData{
public boolean isBST;
public int min;
public int max;
public ReturnData(boolean isBST, int min, int max) {
this.isBST = isBST;
this.min = min;
this.max = max;
}
}
public static ReturnData process(Node x){
if (x == null){
return null;
}
ReturnData left = process(x.left);
ReturnData right = process(x.right);
int min = x.value;
int max = x.value;
if (left!=null){
min=Math.min(min ,left.min);
max=Math.max(max,left.max);
}
if (right!=null){
min=Math.min(min ,right.min);
max=Math.max(max,right.max);
}
boolean isBST = true;
if (left !=null && (!left.isBST || left.max >= x.value)){
isBST = false;
}
if (right !=null && (!right.isBST || x.value>=right.min)){
isBST = false;
}
return new ReturnData(isBST,min,max);
}
套路满二叉树
class Info{
public int height;
public int nodes;
public Info(int h,int n){
height = h;
nodes = n;
}
}
public static boolean isC(Node head){
if(head == null){
return true;
}
Info data = process(head);
return data.nodes == (1 << data.height) - 1;
}
public static Info process(Node x){
if(x == null){
return new Info(0,0)
}
Info left = process(x.left);
Info right = process(x.right);
int height = Math.max(left.height, right.height) + 1;
int nodes = left.nodes + right.nodes + 1;
return new Info(height,nodes);
}
祖先问题
容器法
先生成能找到每一个节点父节点的Hashmap，然后用HashSet存放O1的每一个父辈，最后看O2
public static void process(Node head, HashMap<Node, Node> fathermap){
if( head == null){
return;
}
fathermap.put(head.left, head);
fathermap.put(head.right, head);
process(head.left, fathermap);
process(head.right, fathermap);
}
public static Node lca(Node head, Node o1, Node o2){
HashMap<Node, Node> fathermap = new HashMap<>();
fathermap.put(head,head);
process(head,fathermap);
HashSet<Node> set1 = new HashSet<>();
Node cur = o1;
while(cur != fathermap.get(cur)){
set1.add(cur);
cur = fathermap.get(cur);
}
set1.add(head);
cur = o2;
while(cur != fathermap.get(cur)){
if( set1.contains(fathermap.get(cur) ){
return fathermap.get(cur);
}else{
cur = fathermap.get(cur);
}
}
}
不用容器
分情况：
1.o1是o2的祖先或者o2是o1的祖先
2.o1或者o2不互为祖先
public static Node lowestAncestor(Node head,Node o1,Node o2){
if( head==null || head==o1 || head ==o2){
return head;
}
Node left = lowestAncestor(head.left, o1, o2);
Node right = lowestAncestor(head.right, o1, o2);
if(left!=null && right!=null){
return head;
}
return left!=null ? left : right;
}
后继节点
中序遍历中每个节点后一个节点
注意：==本题中的节点有指向父节点的指针==
分类：
1.当前节点有右树，看右树的最后一个左孩子
2.当前节点无右树，一路向上找父节点，直到找到某个节点是它的父节点的左孩子，但是注意整个树的最右节点无后继节点
用容器
利用中序遍历得到一个序列，在这个序列中去找每一个节点的后继节点
不用容器
public static Node getSuccessorNode(Node node){
if(node == null){
return node;
}
if(node.right != null){
return getleftmost(node.right);
} else {
Node parent = node.parent;
while (parent != null && parent.left != node){
node = parent;
parent = node.parent;
}
return parent;
}
}
public static Node getleftmost(Node node){
if(node == null){
return node;
}
while(node.left != null){
node = node.left;
}
return node;
}
二叉树的序列化和反序列化
内存里的一棵树如何变成字符串形式，又如何从字符串变成内存里的树
public static String serialByPre(Node head){
if(head == null){
return "#_";
}
String res = head.value + "_";
res += serialByPre(head.left);
res += serialByPre(head.right);
return res;
}
public static Node reconByPreString(String preStr){
String[] values = preStr.split("_");
Queue<String> queue = new LinkedList<String>();
for(int i = 0; i != values.lenght; i++){
queue.add(values[i]);
}
return reconPreOrder(queue);
}
public static Node reconPreOrder(Queue<String> queue){
String value = queue.poll;
if(value.equals("#") ){
return null;
}
Node head = new Node(Integer.valueof(value));
head.left = reconPreOrder(queue);
head.right = reconPreOrder(queue);
return head;
}
折纸问题
public static void printProcess(int i,int N,boolean down){
//down为true代表凹，false代表凸
if ( i > N){
return;
}
printProcess(i+1,N,true);
System.out.println(down ? "凹" : "凸");
printProcess(i+1,N,false);
}
