一、概念
二、题目
2.1 把数组转换成二叉树
2.2.1 使用队列方式
public static Node getTreeFromArr2(int[] arr) {
if (arr == null || arr.length == 0) {
return null;
}
LinkedList<Node> quque = new LinkedList<>();
Node root = new Node(arr[0]);
quque.add(root);
int index = 1;
while(!quque.isEmpty()){
// pop 0的时候，刚好操作1、2
// pop 1的时候，刚好操作3、4
// pop 2的时候，刚好操作5、6
Node temp = quque.pop();
if(index < arr.length){
temp.left = new Node(arr[index]);
quque.add(temp.left);
index++;
}
if(index < arr.length){
temp.right = new Node(arr[index]);
quque.add(temp.right);
index++;
}
}
return root;
}
2.2.3 使用堆的方式
private static Node getTreeFromArr(int[] arr) {
Map<Integer, Node> map = new HashMap();
for (int i = arr.length - 1; i >= 0; i--) {
Node temp = new Node(arr[i]);
temp.value = arr[i];
map.put(i, temp);
int leftChildIndex = 2 * i + 1;
int rightChildIndex = 2 * i + 2;
if (leftChildIndex < arr.length) {
temp.left = map.get(leftChildIndex);
}
if (rightChildIndex < arr.length) {
temp.right = map.get(rightChildIndex);
}
}
return map.get(0);
}
2.2 二叉树进行前序、中序、后序遍历
2.2.1 递归的方式
@ToString
public static class Node {
public Node left;
public Node right;
public int value;
public Node(int value) {
this.value = value;
}
}
public static void main(String[] args) {
int[] arr = {0, 1, 2, 3, 4, 5, 6};
// Node head = getTreeFromArr(arr);
Node head2 = getTreeFromArr2(arr);
// System.out.println(JSON.toJSONString(head));
System.out.println(JSON.toJSONString(head2));
/*
前序遍历：[0, 1, 3, 4, 2, 5, 6]
中序遍历：[3, 1, 4, 0, 5, 2, 6]
后序遍历：[3, 4, 1, 5, 6, 2, 0]
*/
preorderPrint(head2);
System.out.println();
inorderPrint(head2);
System.out.println();
postorderPrint(head2);
}
/**
* 前序遍历（中左右）
*/
public static void preorderPrint(Node temp){
if(null == temp){
return;
}
System.out.print(temp.value + ",");
preorderPrint(temp.left);
preorderPrint(temp.right);
}
/**
* 中序遍历（左中右）
*/
public static void inorderPrint(Node temp){
if(null == temp){
return;
}
inorderPrint(temp.left);
System.out.print(temp.value + ",");
inorderPrint(temp.right);
}
/**
* 右序遍历（左中右）
*/
public static void postorderPrint(Node temp){
if(null == temp){
return;
}
postorderPrint(temp.left);
postorderPrint(temp.right);
System.out.print(temp.value + ",");
}
public static Node getTreeFromArr2(int[] arr) {
if (arr == null || arr.length == 0) {
return null;
}
LinkedList<Node> quque = new LinkedList<>();
Node root = new Node(arr[0]);
quque.add(root);
int index = 1;
while(!quque.isEmpty()){
// pop 0的时候，刚好操作1、2
// pop 1的时候，刚好操作3、4
// pop 2的时候，刚好操作5、6
Node temp = quque.pop();
if(index < arr.length){
temp.left = new Node(arr[index]);
quque.add(temp.left);
index++;
}
if(index < arr.length){
temp.right = new Node(arr[index]);
quque.add(temp.right);
index++;
}
}
return root;
}
2.2.2 栈的方式
1、前序遍历（宽度遍历）
/**
* Stack方法
* 前序遍历（中左右）
*/
public static void preorderPrintByStack(Node root) {
Stack<Node> stack = new Stack<>();
stack.push(root);
// 可以不用queue，可以直接打印，省空间 N
// 我加一个 queue的目的是为了后序的翻转好理解
Queue<Node> queue = new LinkedList<>();
while (!stack.isEmpty()) {
Node temp = stack.pop();
// System.out.print(temp.value + ",");
// 此处可以不打印，直接入一个新的 queue
queue.offer(temp);
if (temp.right != null) {
stack.push(temp.right);
}
if (temp.left != null) {
stack.push(temp.left);
}
}
System.out.print("preorderPrintByStack -> ");
while (!queue.isEmpty()) {
System.out.print(queue.poll().value + ",");
}
System.out.println();
}
/**
* 宽度遍历，其实就是中左右，也就是前序遍历
* 用一个 queue 辅助也是可以搞定的
* @param head
*/
public static void widthPrint(Node head){
if(null == head){
return;
}
Queue<Node> queue = new LinkedList<>();
queue.offer(head);
while(!queue.isEmpty()){
Node temp = queue.poll();
System.out.print(temp.value + ",");
if(temp.left != null){
queue.offer(temp.left);
}
if(temp.right != null){
queue.offer(temp.right);
}
}
}
2、中序遍历
/**
* Stack方法
* 中序遍历（左中右）
*/
public static void inOrderPrintByStack(Node root) {
if(null == root){
return;
}
Node current = root;
Stack<Node> stack = new Stack<>();
// 可以不用queue，可以直接打印，省空间 N
// 我加一个 queue的目的是为了后序的翻转好理解
Queue<Node> queue = new LinkedList<>();
while (current != null || !stack.isEmpty()) {
// 如果current不是null，那么就一直往左找下去
while(current != null){
stack.push(current);
current = current.left;
}
current = stack.pop();
// System.out.print(current.value + ",");
queue.offer(current);
// 左边已经干完了，那么就一直往右找
current = current.right;
}
System.out.print("inOrderPrintByStack -> ");
while (!queue.isEmpty()) {
System.out.print(queue.poll().value + ",");
}
}
3、右序遍历
/**
* 右序遍历（左右中）
* 翻过来就是 中右左， 因为前序是中左右，前序是先压right再压left，那么反过来，先压left再压right的话，就会是中右左了
*/
public static void postorderPrintByStack(Node temp) {
if (null == temp) {
return;
}
Stack<Node> stackA = new Stack<>();
stackA.push(temp);
// 注意和之前的区别，上面的中序和前序都是 queue ，FIFO，那么 Stack 的FILO，就能实现这个翻转
Stack<Node> stackB = new Stack<>();
while(!stackA.isEmpty()){
temp = stackA.pop();
stackB.push(temp);
if(temp.left != null){
stackA.push(temp.left);
}
if(temp.right != null){
stackA.push(temp.right);
}
}
System.out.print("postorderPrintByStack -> ");
while (!stackB.isEmpty()) {
System.out.print(stackB.pop().value + ",");
}
}
0、测试代码汇总
@ToString
public static class Node {
public Node left;
public Node right;
public int value;
public Node(int value) {
this.value = value;
}
}
public static void main(String[] args) {
int[] arr = {0, 1, 2, 3, 4, 5, 6};
// Node head = getTreeFromArr(arr);
Node head2 = getTreeFromArr2(arr);
// System.out.println(JSON.toJSONString(head));
System.out.println(JSON.toJSONString(head2));
/*
前序遍历：[0, 1, 3, 4, 2, 5, 6]
中序遍历：[3, 1, 4, 0, 5, 2, 6]
后序遍历：[3, 4, 1, 5, 6, 2, 0]
*/
System.out.println("preorderPrint ->");
preorderPrint(head2);
System.out.println();
System.out.println("inorderPrint ->");
inorderPrint(head2);
System.out.println();
System.out.println("postorderPrint ->");
postorderPrint(head2);
System.out.println();
System.out.println("——————————");
preorderPrintByStack(head2);
inOrderPrintByStack(head2);
postorderPrintByStack(head2);
}
/**
* 前序遍历（中左右）
*/
public static void preorderPrint(Node temp) {
if (null == temp) {
return;
}
System.out.print(temp.value + ",");
preorderPrint(temp.left);
preorderPrint(temp.right);
}
/**
* 中序遍历（左中右）
*/
public static void inorderPrint(Node temp) {
if (null == temp) {
return;
}
inorderPrint(temp.left);
System.out.print(temp.value + ",");
inorderPrint(temp.right);
}
/**
* 右序遍历（左中右）
*/
public static void postorderPrint(Node temp) {
if (null == temp) {
return;
}
postorderPrint(temp.left);
postorderPrint(temp.right);
System.out.print(temp.value + ",");
}
/**
* Stack方法
* 前序遍历（中左右）
*/
public static void preorderPrintByStack(Node root) {
Stack<Node> stack = new Stack<>();
stack.push(root);
// 可以不用queue，可以直接打印，省空间 N
// 我加一个 queue的目的是为了后序的翻转好理解
Queue<Node> queue = new LinkedList<>();
while (!stack.isEmpty()) {
Node temp = stack.pop();
// System.out.print(temp.value + ",");
// 此处可以不打印，直接入一个新的 queue
queue.offer(temp);
if (temp.right != null) {
stack.push(temp.right);
}
if (temp.left != null) {
stack.push(temp.left);
}
}
System.out.print("preorderPrintByStack -> ");
while (!queue.isEmpty()) {
System.out.print(queue.poll().value + ",");
}
System.out.println();
}
/**
* Stack方法
* 中序遍历（左中右）
*/
public static void inOrderPrintByStack(Node root) {
if(null == root){
return;
}
Node current = root;
Stack<Node> stack = new Stack<>();
// 可以不用queue，可以直接打印，省空间 N
// 我加一个 queue的目的是为了后序的翻转好理解
Queue<Node> queue = new LinkedList<>();
while (current != null || !stack.isEmpty()) {
// 如果current不是null，那么就一直往左找下去
while(current != null){
stack.push(current);
current = current.left;
}
current = stack.pop();
// System.out.print(current.value + ",");
queue.offer(current);
// 左边已经干完了，那么就一直往右找
current = current.right;
}
System.out.print("inOrderPrintByStack -> ");
while (!queue.isEmpty()) {
System.out.print(queue.poll().value + ",");
}
}
/**
* 右序遍历（左右中）
* 翻过来就是 中右左， 因为前序是中左右，前序是先压right再压left，那么反过来，先压left再压right的话，就会是中右左了
*/
public static void postorderPrintByStack(Node temp) {
if (null == temp) {
return;
}
Stack<Node> stackA = new Stack<>();
stackA.push(temp);
// 注意和之前的区别，上面的中序和前序都是 queue ，FIFO，那么 Stack 的FILO，就能实现这个翻转
Stack<Node> stackB = new Stack<>();
while(!stackA.isEmpty()){
temp = stackA.pop();
stackB.push(temp);
if(temp.left != null){
stackA.push(temp.left);
}
if(temp.right != null){
stackA.push(temp.right);
}
}
System.out.print("postorderPrintByStack -> ");
while (!stackB.isEmpty()) {
System.out.print(stackB.pop().value + ",");
}
}
public static Node getTreeFromArr2(int[] arr) {
if (arr == null || arr.length == 0) {
return null;
}
LinkedList<Node> quque = new LinkedList<>();
Node root = new Node(arr[0]);
quque.add(root);
int index = 1;
while (!quque.isEmpty()) {
// pop 0的时候，刚好操作1、2
// pop 1的时候，刚好操作3、4
// pop 2的时候，刚好操作5、6
Node temp = quque.pop();
if (index < arr.length) {
temp.left = new Node(arr[index]);
quque.add(temp.left);
index++;
}
if (index < arr.length) {
temp.right = new Node(arr[index]);
quque.add(temp.right);
index++;
}
}
return root;
}
2.3 求一颗二叉树的宽度
private static void getTreeWidth(Node root) {
System.out.println();
System.out.println("---getTreeWidth---");
Node temp = root;
Queue<Node> queue = new LinkedList<>();
queue.offer(temp);
int maxLevelSize = 0;
while (!queue.isEmpty()) {
int levelSize = queue.size();
maxLevelSize = Math.max(maxLevelSize,levelSize);
// 思路就是：for完结束之后，才会进入下一层
for (int i = 0; i < levelSize; i++) {
temp = queue.poll();
System.out.print(temp.value + ",");
if (temp.left != null) {
queue.offer(temp.left);
}
if (temp.right != null) {
queue.offer(temp.right);
}
}
}
System.out.println("maxLevelSize -> " + maxLevelSize);
}
