【算法】图解面试笔试热点二叉树相关算法题汇总
目录
1.前中后序遍历
1.1.递归序实现
1.2.非递归实现
2.二叉树的宽度优先遍历
2.1.求二叉树的最大宽度
3.判断一棵树是否是搜索二叉树
4.判断一棵树是否是完全二叉树
5.判断一棵树是否是满二叉树
6.判断一棵树是否是平衡二叉树
7.最低公共祖先
8.找到后继节点
9.二叉树的序列化与反序列化
10.纸条折痕问题
二叉树的节点结构
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}1.前中后序遍历
1.1.递归序实现
递归的方法遍历二叉树时每一个节点都会被访问三次
public static void f(Node head) {
//第1次访问当前节点
if (head == null) {
return;
}
//第1次访问结束
f(head.left);
//第2次访问当前节点
//第2次访问结束
f(head.right);
//第3次访问当前节点
//第3次访问结束
}
递归序
1,2,4,4,4,2,5,5,5,2,1,3,6,6,6,3,7,7,7,3,1在递归序的基础上衍生出了三种顺序的遍历，先序中序后序
先序：先打印头节点，再打印左子树上所有的节点，最后打印右子树上所有的节点。可以利用递归序，仅当第一次来到一个节点时才打印
public static void preOrderRecur(Node head) {
if (head == null) {
return;
}
System.out.print(head.value + " ");
preOrderRecur(head.left);
preOrderRecur(head.right);
}先序(根左右)
1,2,4,5,3,6,7中序：先打印左子树上所有的节点，再打印头节点，最后打印右子树上所有的节点。可以利用递归序，仅当第二次来到一个节点时才打印
public static void inOrderRecur(Node head) {
if (head == null) {
return;
}
inOrderRecur(head.left);
System.out.print(head.value + " ");
inOrderRecur(head.right);
}//中序(左根右)
4,2,5,1,6,3,7后序：先打印左子树上所有的节点，再打印右子树上所有的节点，最后打印头节点。可以利用递归序，仅当第三次来到一个节点时才打印
public static void posOrderRecur(Node head) {
if (head == null) {
return;
}
posOrderRecur(head.left);
posOrderRecur(head.right);
System.out.print(head.value + " ");
}//后序(左右根)
4,5,2,6,7,3,11.2.非递归实现
准备一个栈
-
先序遍历
首先根节点入栈
(1) 每次从栈中弹出一个节点cur
(2) 处理（打印）cur
(3) 如果可以，先把右孩子压入栈，再把左孩子压入栈
(4) 重复这个过程
public static void preOrderRecur(Node head) {
if (head != null) {
Stack<Node> stack = new Stack<Node>();
stack.add(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);
}
}
}
System.out.println();
}-
后序遍历
我们在先序遍历中做以下改动
额外准备一个收集栈（总共有两个栈）
首先根节点入栈
(1) 每次从栈中弹出一个节点cur
(2) 把cur放入收集栈中
(3) 如果可以，先把左孩子压入栈中，再把右孩子压入栈中
(4) 重复这个过程
(5) 弹出收集栈中的所有元素并打印
public static void posOrderUnRecur1(Node head) {
if (head != null) {
Stack<Node> s1 = new Stack<Node>();
Stack<Node> s2 = new Stack<Node>();
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.print(s2.pop().value + " ");
}
}
System.out.println();
}-
中序遍历
先把整棵树的左边界全部压入栈，左边界指从当前根节点开始一直.left直至null
在依次弹出并打印节点的过程中对当前节点的右子树重复这个操作
public static void inOrderUnRecur(Node head) {
if (head != null) {
Stack<Node> stack = new Stack<Node>();
while (!stack.isEmpty() || head != null) {
if (head != null) {
stack.push(head);
head = head.left;
} else {
head = stack.pop();
System.out.print(head.value + " ");
head = head.right;
}
}
}
System.out.println();
}2.二叉树的宽度优先遍历
先序遍历就是二叉树的深度优先遍历
宽度优先遍历
初始化一个队列
(1) 先把头节点存入队列
(2) 每一次拿出节点并打印，同时先把左子树存入队列，再把右子树存入队列
public static void w(Node head) {
if (head == null) {
return;
}
Queue<Node> queue = new LinkedList<>();
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);
}
}
}2.1.求二叉树的最大宽度
(1) 使用哈希表
需要一个机制来确定遍历的过程中，当前层的宽度是多少，即确定当前节点属于第几层。准备一张表，记录当前节点属于第几层
public static int w(Node head) {
if (head == null) {
return 0;
}
Queue<Node> queue = new LinkedList<>();
queue.add(head);
HashMap<Node, Integer> levelMap = new HashMap<>();
levelMap.put(head, 1);
int curLevel = 1; //当前处于第几层
int curlevelNodes = 0; //当前层有几个节点
int max = Integer.MIN_VALUE;
while (!queue.isEmpty()) {
Node cur = queue.poll();
int curNodeLevel = levelMap.get(cur);
if (curNodeLevel == curLevel) {
curLevelNodes++;
} else {
max = Math.max(max, curLevelNodes);
curLevel++;
curLevelNodes = 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;
}(2) 使用队列
第一个变量：当前层最后一个节点 Node curEnd
当前遍历的节点所在的层中，这一层的最后一个节点是谁
第二个变量：下一层最后一个节点 Node nextEnd
当前遍历的节点所在的层中，下一层的最后一个节点是谁
第三个变量：当前层已经发现的节点数 int curLevel
第四个变量：全局变量 int max
略
3.判断一棵树是否是搜索二叉树
搜索二叉树（二叉排序树）的特点是左子树全部小于根节点，右子树全部大于根节点
如果中序遍历的结果是升序的，那么这棵二叉树就是搜索二叉树
(1) 递归
-
方法一
//全局变量保存上一个节点的值
public static int preValue = Integer.MIN_VALUE;
public static boolean isBST(Node head) {
if (head == null) {
return true;
}
boolean isLeftBst = isBST(head.left);
if (!isLeftBst) {
return false;
}
if (head.value <= preValue) {
return false;
} else {
preValue = head.value;
}
return isBST(head.right);
}-
方法二
-
树型DP
一棵搜索二叉树：
(1) 左子树是搜索二叉树
(2) 右子树是搜索二叉树
(3) 左子树的最大值小于当前节点
(4) 右子树的最小值大于当前节点
左子树与右子树需要提供的信息是一样的：自己是否是搜索二叉树？自己的最大值是多少？自己的最小值是多少？
//信息体
public static class ReturnData {
public boolean isBST;
public int min;
public int max;
public ReturnData(boolean is, int mi, int ma) {
isBST = is;
min = mi;
max = ma;
}
}public static ReturnData process(Node x) {
if (x == null) {
return null;
}
ReturnData leftData = process(x.left);
ReturnData rightData = process(x.right);
int min = x.value;
int max = x.value;
if (leftData != null) {
min = Math.min(min, leftData.min);
max = Math.max(max, leftData.max);
}
if (rightData != null) {
min = Math.min(min, rightData.min);
max = Math.max(max, rightData.max);
}
boolean isBST= true;
if (leftData != null && (!leftData.isBST || leftData.max >= x.value)) {
isBST = false;
}
if (rightData != null && (!rightData.isBST || x.value >= rightData.min)) {
isBST = false;
}
return new ReturnData(isBST, min, max);
}(2) 非递归
public static boolean isBST2(Node head) {
if (head != null) {
int preValue = Integer.MIN_VALUE;
Stack<Node> stack = new Stack<>();
while (!stack.isEmpty() || head != null) {
if (head != null) {
stack.push(head);
head = head.left;
} else {
head = stack.pop();
if (head.value <= preValue) {
return false;
} else {
preValue = head.value;
}
head = head.right;
}
}
}
return true;
}4.判断一棵树是否是完全二叉树
完全二叉树要么是满二叉树，要么是从左往右依次变满的二叉树
按照宽度遍历二叉树
(1) 任何一个节点，有右孩子却无左孩子则返回false
(2) 如果遇到了第一个左右孩子不全的情况，接下来的所有节点都必须是叶子结点
public static boolean isCBT(Node head) {
if (head == null) {
return true;
}
LinkedList<Node> queue = new LinkedList<>();
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;
}
}
return true;
}5.判断一棵树是否是满二叉树
设最大深度L，节点数N
满二叉树满足 N = (2^L) - 1
-
树型DP
//信息体
public static class Info {
public int height;
public int nodes;
public Info(int h, int n) {
height = h;
nodes = n;
}
}public static Info f(Node) {
if (x == null) {
return new Info(0, 0);
}
Info leftData = f(x.left);
Info rightData = f(x.right);
int height = Math.max(leftData.height, rightData.height) + 1;
int nodes = leftData.nodes + rightData.nodes + 1;
return new Info(height, nodes);
}public static boolean isF(Node head) {
if (head == null) {
return true;
}
Info data = f(head);
return data.nodes == (1 << data.height - 1);
}6.判断一棵树是否是平衡二叉树
对于平衡二叉树来说，任何一棵子树左右子树的高度差都不超过1
-
树型DP
一棵平衡二叉树：
(1) 左子树是平衡二叉树
(2) 右子树是平衡二叉树
(3) 左右子树的高度差不超过1
左子树与右子树需要提供的信息是一样的：自己是否是平衡的？自己的高度是多少？
//信息体
public static class ReturnType {
public boolean isBalanced;
public int height;
public ReturnType(boolean isB, int hei) {
isBalanced = isB;
height = hei;
}
}public static ReturnType process(Node x) {
if (x == null) {
return new ReturnType(true, 0);
}
ReturnType leftData = process(x.left);
ReturnType rightData = process(x.right);
int height = Math.max(leftData.height, rightData.height) + 1;
boolean isBalanced = leftData.isBalanced && rightData.isBalanced && Math.abs(leftData.height - rightData.height) < 2;
return new ReturnType(isBalanced, height);
}7.最低公共祖先
问：
给定两个二叉树的节点node1和node2，找到他们的最低公共祖先节点，例：下图中D与G的最低公共祖先为B，E与G的最低公共祖先为E
答：
找到两个节点所在的链最初汇聚的节点
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 = lowestAcestor(head.right, o1, o2);
if (left != null && right != null) {
return head;
}
return left != null ? left : right;
}8.找到后继节点
问：
在二叉树中找到一个节点的后继节点
现在有一种新的二叉树节点类型如下
public class Node {
public int value;
public Node left;
public Node right;
public Node parent;
public Node (int val) {
value = val;
}
}该结构比普通二叉树节点结构多了一个指向父节点的parent指针
假设有一棵Node类型的节点组成的二叉树，树中每个节点的parent指针都正确地指向自己的父节点，头节点的parent指向null
只给一个在二叉树中的某个节点node，请实现返回node的后继节点的函数
在中序遍历中，节点的下一个节点叫做后继节点，节点的前一个节点叫做前驱节点
答：
D的后继节点是B、B的后继节点是E、E的后继节点是A...
(1) 当x有右子树时，x的后继是右子树上的最左节点
(2) 当x无右子树时，从x开始，检查自己是不是父节点的左孩子，如果不是则继续向上检查，是则返回父节点
(3) 整棵树最右面的节点是没有后继的，它的后继为null
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) {
noed = node.left;
}
return node;
}9.二叉树的序列化与反序列化
问：
内存里的一棵树如何变成字符串形式，又如何从字符串形式变成内存里的树
答：
先序遍历方式序列化，下划线表示一个值的结束
public static String serialByPre(Node head) {
if (head == null) {
return "#_";
}
String res = head.value + "_";
res += serialByPre(head.left);
res += serialByPre(head.righht);
return res;
}public static Node reconByPreString(String preStr) {
String[] values = preStr.split("_");
Queue<String> queue = new LinkedList<String>();
for (int i = 0; i != values.length; i++) {
queue.add(values[i]);
}
return reconPreOrder(queue);
}public static Node recponPreOrder(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;
}10.纸条折痕问题
问：
将一根纸条竖起来，每次向自己的方向对折，假设对折N次，输出凹折痕与凸折痕的分布情况
答：
不管当前折痕为凹还是为凸，该折痕的左子节点必定为凹折痕，右子节点必定为凸折痕
将二叉树中序遍历即可
//递归过程，来到了某一节点
//i是节点的层数，N是总共有几层，down == true则凹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 printAllFolds(int N) {
printProcess(1, N, true);
}