结构
class Node{
int value;
Node left;
Node right;
public Node(int value){
this.value = value;
}
}
二叉树的遍历
对于所有子树来说,递归思想
理解:对于所有子树来说,都要符合某个序遍历的顺序
先序:先头结点->左子树->右子树
/**
* 先序遍历
* @param head
*/
public void preOrder(Node head){
if(head == null){
return;
}
System.out.print(head.value+"=>");
preOrder(head.left);
preOrder(head.right);
}
中序:左子树->头结点->右子树
/**
* 中序遍历
* @param head
*/
public void midOrder(Node head){
if(head == null){
return;
}
midOrder(head.left);
System.out.print(head.value+"=>");
midOrder(head.right);
}
后序:左子树->右子树->头结点
/**
* 后序遍历
* @param head
*/
public void posOrder(Node head){
if(head == null){
return;
}
posOrder(head.left);
posOrder(head.right);
System.out.print(head.value+"=>");
}
递归序:根据递归逻辑遍历了整个树(每一个节点都会到达三次)
先序:第一次到达一个节点打印
中序:第二次到达一个节点
后序:第三次到达一个节点
image.png
如上图(忽略里面的数字顺序):
递归序,寻找节点为(本身节点->左子节点->右子节点)
A->B->D->G->G(G的左子节点未找到回到G)->G(G的右子节点未找到回到G)->D->H->H->H->D->B->B->A->C->E->E->I->I->I->E->C->F->F->F->C->A
每一个节点都到达了三次
先序遍历(第一次到达节点打印即为)=A,B,D,G,H,C,E,I,F
中序遍历(第二次到达节点打印)=G,D,H,B,A,E,I,C,F
后序遍历(第三次到达节点打印)=G,H,D,B,I,E,F,C,A
非递归的方式实现先序,中序和后序
1.任何递归方式都可以改成非递归
2.自己设计压栈的方式实现
1.先序
1.1利用压栈方式
1.1弹出就打印
1.2.先右后左(弹出时即先左后右)
/**
* 先序遍历(压栈)
* @param head
*/
public void preOrder(Node head){
if(head == null){
return;
}
Stack<Node> stack = new Stack<>();
stack.push(head);
while(!stack.isEmpty()){
head = stack.pop();
System.out.print(head.value + "=>");
if(head.right != null){
stack.push(head.right);
}
if(head.left != null){
stack.push(head.left);
}
}
}
实现(后序):
方式1:
1.弹出压入另一个栈
2.先左后右
3.逆序返回另一个栈
理解:先序为根->右->左进栈,后序为左->右->根进栈,正好为先序栈的逆序情况
/**
* 后序实现1
* @param head
*/
public void after1(Node head){
if(head == null){
return;
}
Stack<Node> stack = new Stack<>();
Stack<Node> rever = new Stack<>();
stack.push(head);
while(!stack.isEmpty()){
head = stack.pop();
rever.push(head);
if(head.left != null){
stack.push(head.left);
}
if(head.right != null){
stack.push(head.right);
}
}
while(!rever.isEmpty()){
System.out.print(rever.pop().value + "=>");
}
}
方式2:
用两个指针head,cur标记是否左右头子树被输出过了
head指向上次被处理过的节点
public void after2(Node head){
if(head == null){
return;
}
Stack<Node> stack = new Stack<>();
stack.push(head);
Node cur = null;
while(!stack.isEmpty()){
cur = stack.peek();
if(cur.left != null && head != cur.left && head != cur.right){
stack.push(cur.left);
}else if(cur.right != null && head != cur.right){
stack.push(cur.right);
}else{
System.out.print(stack.pop().value + "=>");
head = cur;
}
}
}
实现(中序):
1.整条左边界依次进栈
2.弹出再进入右节点
整棵树可以被左边界拆解,对于栈中数据,都是先左后头
/**
* 中序遍历
* @param head
*/
public void midOrder(Node head){
if(head == null){
return;
}
Stack<Node> stack = new Stack<>();
Node cur = head;
while(!stack.isEmpty() || cur != null){
if(cur != null){
stack.push(cur);
cur = cur.left;
}else{
cur = stack.pop();
System.out.print(cur.value + "=>");
cur = cur.right;
}
}
}
按层遍历(宽度优先遍历)
队列方式:一层一层加,从左到右
/**
* 按层遍历二叉树
* @param head
*/
public void fl(Node head){
if(head == null){
return;
}
Queue<Node> queue = new LinkedList<>();
queue.add(head);
while(!queue.isEmpty()){
head = queue.poll();
System.out.print(head.value + "=>");
if(head.left != null){
queue.add(head.left);
}
if(head.right != null){
queue.add(head.right);
}
}
}
题目:哪一层宽度最大,宽度为多少
解析:
方式1:用map的方式,key是Node,value是哪一层
2.变量哪一层,层宽度,全局最大宽度
/**
* 求层最大宽度
* @param head
*/
public int maxWidth(Node head){
if(head == null){
throw new RuntimeException("二叉树为空");
}
//层最大宽度
int max = 0;
//key=node,value=node所在的层
Map<Node,Integer> map = new HashMap<>();
map.put(head,1);
Queue<Node> queue = new LinkedList<>();
queue.add(head);
//当前所在哪一层
int curLevel = 1;
//当前层的最大宽度
int curLevelWidth = 0;
while(!queue.isEmpty()){
head = queue.poll();
//此节点在哪一层
int curNodeLevel = map.get(head);
if (head.left != null){
map.put(head.left,curNodeLevel + 1);
queue.add(head.left);
}
if (head.right != null){
map.put(head.right,curNodeLevel + 1);
queue.add(head.right);
}
//如果还在当前层,宽度就++
if(curLevel == curNodeLevel){
curLevelWidth++;
}else{//如果不在当前层,说明将进入下一层,比较记录当前层的最大宽度与整体最大宽度
max = Math.max(curLevelWidth,max);
curLevel++;
curLevelWidth = 1;
}
}
return max;
}
方式二:1.当前层最右节点
2.下一层最右节点
3.每一个节点找下一层的最右节点
/**
* 不使用map求层最大宽度
* @param head
*/
public int maxWidthNoMap(Node head){
if(head == null){
throw new RuntimeException("二叉树不存在");
}
int max = 0;
Queue<Node> queue = new LinkedList<>();
queue.add(head);
//当前层最右节点
Node curEnd = head;
//下一层最右节点
Node nextEnd = head;
//层宽
int curNodeWidth = 0;
while(!queue.isEmpty()){
Node cur = queue.poll();
if (cur.left != null){
queue.add(cur.left);
nextEnd = cur.left;
}
if (cur.right != null){
queue.add(cur.right);
nextEnd = cur.right;
}
curNodeWidth++;
//如果已经到了当前层最右节点,则进行结算
if (cur == curEnd){
max = Math.max(max,curNodeWidth);
//重置当前层最右节点到下一层最右节点
curEnd = nextEnd;
curNodeWidth = 0;
}
}
return max;
}
二叉树的序列化和反序列化
1,可以用先序和后序遍历,实现序列化(需要加空节点)
2.反序列化同理
3.中序方式则不行
如:
* __2
* /
* 1
* 和
* 1__
* \
* 2
补足空位置的中序遍历结果都是{ null, 1, null, 2, null}
public Queue<Node> serializble(Node head){
if(head == null){
return null;
}
Queue<Node> queue = new LinkedList<>();
serialerByPreOrder(head,queue);
return queue;
}
/**
* 先序方式进行序列化二叉树
* @param head
* @param queue
*/
private void serialerByPreOrder(Node head, Queue<Node> queue) {
if(head == null){
queue.add(head);
return;
}
queue.add(head);
serialerByPreOrder(head.left,queue);
serialerByPreOrder(head.right,queue);
}
先序方式进行反序列化
后序方式进行反序列化,需将nodes列表中的节点放入栈中,用栈来实现序列化
/**
* 先序方式进行反序列化
* @param nodes
* @return
*/
public Node buildByPreOrder(Queue<Node> nodes){
if (nodes == null || nodes.size() == 0){
return null;
}
Node head = preb(nodes);
return head;
}
private Node preb(Queue<Node> nodes) {
Node poll = nodes.poll();
if (poll == null){
return null;
}
poll.left = preb(nodes);
poll.right = preb(nodes);
return poll;
}
后序方式反序列化
public Node buildByPosOrder(Queue<Integer> nodes){
if(nodes == null || nodes.size() == 0){
return null;
}
//先序为 头->左->右 放入栈中弹出即为 右->左->头
Stack<Integer> stack = new Stack<>();
while(!nodes.isEmpty()){
stack.add(nodes.poll());
}
Node head = prob(stack);
return head;
}
private Node prob(Stack<Integer> stack) {
Integer pop = stack.pop();
if(pop == null){
return null;
}
//弹出 右->左的顺序,设置也先设置右,后设置左
Node head = new Node(pop);
head.right = prob(stack);
head.left = prob(stack);
return head;
}
按层序列化
public Queue<Node> serializer(Node head){
if(head == null){
return null;
}
//用户按层遍历的队列
Queue<Node> queue = new LinkedList<>();
//序列化后的队列
Queue<Node> nodes = new LinkedList<>();
queue.add(head);
while(!queue.isEmpty()){
//从层队列弹出放入序列化队列
Node poll = queue.poll();
nodes.add(poll);
//如果poll为null,说明没有节点,继续弹出
while (poll == null && !queue.isEmpty()){
poll = queue.poll();
nodes.add(poll);
}
//队列弹空还为null,说明到了最后一个节点,直接跳出
if (poll == null){
break;
}
queue.add(poll.left);
queue.add(poll.right);
}
return nodes;
}
按层进行反序列化
/**
* 按层进行反序列化
* @param levelList
* @return
*/
public static Node buildByLevelQueue(Queue<String> levelList) {
if (levelList == null || levelList.size() == 0) {
return null;
}
Node head = generateNode(levelList.poll());
Queue<Node> queue = new LinkedList<Node>();
if (head != null) {
queue.add(head);
}
Node node = null;
while (!queue.isEmpty()) {
node = queue.poll();
node.left = generateNode(levelList.poll());
node.right = generateNode(levelList.poll());
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
return head;
}
public static Node generateNode(String val) {
if (val == null) {
return null;
}
return new Node(Integer.valueOf(val));
}
