二叉树（Binary tree）是一种非常重要的数据结构，更是算法题中高频出现的知识点，不管是为了应付工作还是面试，都有必要深度学习一下。
注意：二叉树的先序、中序、后续和层序遍历是做算法的基础，非常有必要先掌握好，一定要理解原理，做起题目来才能得心应手。有需要的小伙伴，请先学习下这篇文章：
Java实现二叉树的先序、中序、后序、层序遍历（递归+非递归方法），附带自己深入浅出的讲解
本文整理了大厂面试中比较多见二叉树面试题，如果遇到更新颖的题目，欢迎大家留言或者私信我，发出来大家一起学习下。
1. 二叉树的【深度】 题目描述：给定一个二叉树，找出其【最小】深度 。 解题 思路：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
public int minDepth(TreeNode root){
if (root == null) {
return 0;
}
int left = minDepth(root.left);
int right = minDepth(root.right);
return Math.min(left, right) + 1;
}
题目描述：换一下，给定一个二叉树，找出其【最大】深度 ？
解题
思路：从根结点到叶结点依次经过的结点 （含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
public int maxDepth(TreeNode root){
if (root == null) {
return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left, right) + 1;
}
2. 判断二叉树是否是【平衡】二叉树
题目描述
：输入一棵二叉树，判断该二叉树是否是平衡二叉树。
解题
思路：平衡二叉树的条件：左子树是平衡二叉树，右子树是平衡二叉树，左右子树高度不超过 1。
注意
：本题使用到了【计算二叉树最大深度】的算法。
public boolean isBalanced(TreeNode root) {
if(root == null) {
return true;
}
boolean condition = Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1;
return condition && isBalanced(root.left) && isBalanced(root.right);
}
// 求二叉树最大深度的方法
public int maxDepth(TreeNode root){
if (root == null) {
return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left, right) + 1;
}
3. 判断二叉树是否是【镜像】二叉树
题目描述： *** 作给定的二叉树，判断二叉树是否为源镜像二叉树。
解题
思路：使用递归方式，比较左子树的left节点和右子树right节点，以及左子树的right节点和右子树left节点是否相等，都相等就是镜像。
复杂度
：间复杂度 - O(n)
，空间复杂度 -
O(n)。
注意：本题和【
判断二叉树 A 中是否包含子树 B
】的算法有很大共同点。
public boolean isSymmetric(TreeNode root) {
return root == null || this.isMirror(root.left, root.right);
}
private boolean isMirror(TreeNode leftNode, TreeNode rightNode) {
if (leftNode == null && rightNode == null) {
return true;
}
if (leftNode == null || rightNode == null) {
return false;
}
if (leftNode.val != rightNode.val) {
return false;
}
// 注意：因为要判断是否对称，所以对比左右和右左是否相等
return isMirror(leftNode.left, rightNode.right) && isMirror(leftNode.right, rightNode.left);
}
4. 判断二叉树 A 中是否包含子树 B
题目描述：输入两棵二叉树 A
，
B
，判断
B
是不是
A
的子结构。（约定空树不是任意一个树的子结构）。
解题
思路：若根节点相等，利用递归比较他们的子树是否相等，若根节点不相等，则利用递归分别在左右子树中查找。doesTree1HaveTree() 和 isMirror() 方法很类似，但是前者对比的是同位置，后者对比的是对称位置。
注意：本题和【
判断二叉树是否是镜像二叉树
】的算法有很大共同点。
public boolean hasSubTree(TreeNode source, TreeNode target) {
if (target == null) {
return true;
}
if (source == null) {
return false;
}
if (doesTree1HaveTree(source, target)) {
return true;
}
return hasSubTree(source.left, target) || hasSubTree(source.right, target);
}
private boolean doesTree1HaveTree(TreeNode source, TreeNode target) {
if (source == null && target == null) {
return true;
}
if (source == null || target == null) {
return false;
}
if (source.val != target.val) {
return false;
}
// 注意：因为要判断是否相同，所以对比左左和右右是否相等
return doesTree1HaveTree(source.left, target.left) && doesTree1HaveTree(source.right, target.right);
}
5. 二叉树的【多行输出】
题目描述：从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
解题
思路：利用辅助空间链表或队列来存储节点，每层输出。
public ArrayList> printTree_61(TreeNode pRoot) {
ArrayList> res = new ArrayList<>();
if (pRoot == null) {
return res;
}
// start 记录从队列中取出的节点数量，end记录每行的节点数
int start = 0; // 还没开始从queue取数据，所以初始值是0
int end = 1; // 根节点只有1个，初始值是1
Queue queue = new linkedList<>();
queue.add(pRoot);
// 行数据临时存储的List
List tempList = new ArrayList<>();
while(!queue.isEmpty()){
TreeNode temp = queue.poll();
tempList.add(temp.val);
start ++;
if (temp.left != null) {
queue.add(temp.left);
}
if (temp.right != null) {
queue.add(temp.right);
}
// 当从队列中取出的数量等于存入的父节点数量时，说明当前层已经遍历完，换行
if (end == start) {
res.add(new ArrayList<>(tempList));
end = queue.size();
start = 0;
tempList.clear();
}
}
return res;
}
5. 二叉树的【序列化】
题目描述：请实现两个函数，分别用来序列化和反序列化二叉树。
解题
思路：序列化 - 前序遍历二叉树存入字符串中；反序列化 - 根据前序遍历重建二叉树。
public static StringBuffer sb = new StringBuffer();
public static String Serialize(TreeNode root) {
if (root == null){
sb.append("#,");
return sb.toString();
}
sb.append(root.val + ",");
Serialize(root.left);
Serialize(root.right);
return sb.toString();
}
public static int index = -1;
public static TreeNode Deserialize(String str) {
index++;
int len = str.length();
String[] strr = str.split(",");
TreeNode node = null;
if (index >= len){
return null;
}
if (!strr[index].equals("#")){
node = new TreeNode(Integer.valueOf(strr[index]));
node.left = Deserialize(str);
node.right = Deserialize(str);
}
return node;
}
6. 二叉树中和为某值的【路径】
题目描述：输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下
一直到叶结点所经过的结点形成一条完整路径。
解题
思路：先保存根节点，然后分别递归在左右子树中找目标值，若找到即到达叶子节点，打印路径中的值。
private static ArrayList> listAll = new ArrayList<>();
private static ArrayList list = new ArrayList<>();
public static ArrayList> FindPath(TreeNode root, int target) {
if (root == null) {
return listAll;
}
list.add(root.val);
target -= root.val;
// 必须是到子节点的完整路径，所以要满足 root.left，root.right 都为null
if (target == 0 && root.left == null && root.right == null) {
listAll.add(new ArrayList<>(list));
}
FindPath(root.left, target);
FindPath(root.right, target);
// 回退：走完一条路径，清空list
list.remove(list.size() - 1);
return listAll;
}
总结
- 上面没有列举前序、中序、后序和层序遍历方法，因为有另外一篇文章写的更详细：Java实现二叉树的先序、中序、后序、层序遍历（递归+非递归方法），附带自己深入浅出的讲解
- 欢迎大家留言补充~~
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）