事实证明不能十题的
- 树前中后序列 递归非递归+层序遍历+按层输出
package offer;
import java.util.*;
//树节点定义
class Node {
public String value;
public Node right;
public Node left;
public Node(String value) {
this.value = value;
}
}
public class Test6 {
//先序 递归
public static void preOrder(Node root) {
if (root == null)
return;
System.out.print(root.value);
preOrder(root.left);
preOrder(root.right);
}
//用栈的形式把递归转写
public static void preOrder2(Node root) {
//如果为空就返回
if (root == null) return;
//命名一个节点
Stack stack = new Stack<>();
//把根节点放进来
stack.push(root);
//访问站点是否为空
//先进后出 所以先右边后左边
while (!stack.isEmpty()) {
Node node = stack.pop();
System.out.print(node.value);
if (node.right != null)
stack.push(node.right);
if (node.left != null)
stack.push(node.left);
}
}
//中序
public static void midOrder(Node root) {
if (root == null)
return;
midOrder(root.left);
System.out.print(root.value);
midOrder(root.right);
}
//非递归中序 找最左节点
public static void midOrder2(Node root) {
//如果为空就返回
if (root == null) return;
//命名一个节点
Stack stack = new Stack<>();
//找到最左节点
Node cur = root;
//一直向左走
while (!stack.isEmpty() || cur != null) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
Node node = stack.pop();
System.out.print(node.value);
if (node.right != null)
cur = node.right;
}
}
//后序
public static void postOrder(Node root) {
if (root == null)
return;
postOrder(root.left);
postOrder(root.right);
System.out.print(root.value);
}
//非递归实现后序遍历
//先序 根左右 根右左逆序
//后续 左右根
public static void postOrder2(Node root) {
if (root == null)
return;
Stack stack = new Stack<>();
//更改后逆序
Stack stack2 = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
Node node = stack.pop();
stack2.push(node);
if (node.left != null)
stack.push(node.left);
if (node.right != null)
stack.push(node.right);
}
while (!stack2.isEmpty()) {
System.out.print(stack2.pop().value);
}
}
//层序遍历
//队里的格式一层层读
private static void bfs(Node root) {
if (root == null)
return;
Queue queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
//打印
Node node = queue.poll();
//访问左右孩子
System.out.println(node.value);
if (node.left != null)
queue.add(node.left);
if (node.right != null)
queue.add(node.right);
}
}
//一层层输出层序遍历 记录queue每一层的大小
//队里的格式一层层读
private static List> bfs2(Node root) {
List> res = new ArrayList<>();
if (root == null)
return res;
Queue queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
List res1 = new ArrayList<>();
while (size-- > 0) {
//打印
Node tmp = queue.poll();
res1.add(tmp.value);
//访问左右孩子
if (tmp.left != null)
queue.add(tmp.left);
if (tmp.right != null)
queue.add(tmp.right);
}
res.add(res1);
}
return res;
}
public static void main(String[] args) {
Node nodeA = new Node("A");
Node nodeB = new Node("B");
Node nodeC = new Node("C");
Node nodeD = new Node("D");
Node nodeE = new Node("E");
Node nodeF = new Node("F");
Node nodeG = new Node("G");
nodeA.left = nodeB;
nodeA.right = nodeC;
nodeB.left = nodeD;
nodeB.right = nodeE;
nodeC.right = nodeF;
nodeE.left = nodeG;
// preOrder(nodeA);
// preOrder2(nodeA);
// midOrder2(nodeA);
// postOrder(nodeA);
// postOrder2(nodeA);
System.out.println(bfs2(nodeA));
}
}
两个栈实现队列
package offer;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
//两个栈实现队列先进先出
class Queue {
private Stack stackA = new Stack<>();
private Stack stackB = new Stack<>();
public void push(int element) {
stackA.push(element);
}
//出队操作
public Integer pop() {
//如果stackB空 A不为空
while (stackB.isEmpty()) {
while (!stackA.isEmpty()) {
//把A中弹出的放到B里面
stackB.push(stackA.pop());
}
}
//如果两个都是空的
if (stackB.isEmpty())
return -1;
else return stackB.pop();
}
}
public class Test7 {
public static void main(String[] args) {
Queue q1 = new Queue();
q1.push(1);
q1.push(2);
q1.push(3);
System.out.println(q1.pop());
System.out.println(q1.pop());
System.out.println(q1.pop());
}
}



