- A+
1 TreeMap和TreeSet在排序时如何比较元素？Collections工具类中的sort()方法如何比较元素？
考察点：Tree
参考回答：
TreeSet要求存放的对象所属的类必须实现Comparable接口，该接口提供了比较元素的compareTo()方法，当插入元素时会回调该方法比较元素的大小。TreeMap要求存放的键值对映射的键必须实现Comparable接口从而根据键对元素进行排序。Collections工具类的sort方法有两种重载的形式，第一种要求传入的待排序容器中存放的对象比较实现Comparable接口以实现元素的比较；第二种不强制性的要求容器中的元素必须可比较，但是要求传入第二个参数，参数是Comparator接口的子类型（需要重写compare方法实现元素的比较），相当于一个临时定义的排序规则，其实就是通过接口注入比较元素大小的算法，也是对回调模式的应用（Java中对函数式编程的支持）。
public class
Student implements Comparable<Student> {
private String name; // 姓名
private int age; // 年龄
public Student(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "Student [name=" + name + ", age=" + age + "]";
}
@Override
public int compareTo(Student o) {
return this.age - o.age; // 比较年龄(年龄的升序)
}
}
import java.util.Set;
import java.util.TreeSet;
class Test01 {
public static void main(String[] args) {
Set<Student> set = new TreeSet<>(); // Java 7
}
}
import java.util.Set;
import java.util.TreeSet;
class Test01 {
public static void main(String[] args) {
Set<Student> set = new TreeSet<>(); // Java 7的钻石语法(构造器后面的尖括号中不需要写类型)
set.add(new Student("Hao LUO", 33));
set.add(new Student("XJ WANG", 32));
set.add(new Student("Bruce LEE", 60));
set.add(new Student("Bob YANG", 22));
for(Student stu : set) {
System.out.println(stu);
}
//
set.add(new Student("Hao LUO", 33));
set.add(new Student("XJ WANG", 32));
set.add(new Student("Bruce LEE", 60));
set.add(new Student("Bob YANG", 22));
for(Student stu : set) {
System.out.println(stu);
}
// 输出结果:
// Student [name=Bob YANG, age=22]
// Student [name=XJ WANG, age=32]
// Student [name=Hao LUO, age=33]
// Student [name=Bruce LEE, age=60]
}
}
// Student [name=Bob YANG, age=22]
// Student [name=XJ WANG, age=32]
// Student [name=Hao LUO, age=33]
// Student [name=Bruce LEE, age=60]
}
}
2 如何打印二叉树每层的节点？
考察点：二叉树
注意：面试中一般写核心代码，另外就是可以问一下面试是输出ArrayList还是int数组。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
public int[] levelOrder(TreeNode root) {
// 如果root为空直接返回
if(root == null){
return new int[0];
}
// 层次遍历
// 队列
Deque<TreeNode> deque = new LinkedList<>();
// 存每一层节点
ArrayList<Integer> temp = new ArrayList<>();
// 根节点入队
deque.offer(root);
while(!deque.isEmpty()){
int size = deque.size();
for(int i=0;i<size;i++) {
//层次遍历
TreeNode curroot = deque.pop();
temp.add(curroot.val);
// 做节点是否为空
if(curroot.left!=null)
deque.offer(curroot.left);
if(curroot.right!=null)
deque.offer(curroot.right);
}
}
// 如果要求返回int数组 就写上这一步，如果没有要求可以直接返回temp即可。
int []result = new int[temp.size()];
for(int i=0;i<result.length;i++){
result[i] = temp.get(i);
}
return result;
}
}
3 如何知道二叉树的深度？
考察点：二叉树
参考回答：
求二叉树的深度方式有两种，递归以及非递归。(出自剑指offer)
①递归实现：
为了求树的深度，可以先求其左子树的深度和右子树的深度，可以用递归实现，递归的出口就是节点为空。返回值为0；
/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
public class Solution {
public int TreeDepth(TreeNode root) {
if(root==null) return 0;
int left = TreeDepth(root.left);
int right = TreeDepth(root.right);
return (left>right)?(left+1):(right+1);
}
}
②非递归实现：
利用层次遍历的算法，将每一层的所有节点放入队列中，在将每一层节点的左右子节点存入放入到队列中，用一个变量记录树的高度即可。
import java.util.*;
public class Solution {
public int TreeDepth(TreeNode root) {
if(root==null)
return 0;
Queue<TreeNode> result = new LinkedList<>();
result.add(root);
int height = 0;
while(!result.isEmpty()){
//获取当前的根节点
int size = result.size();
while(size>0){
//遍历当前层，将该层的子节点都加入队列中
TreeNode nowroot = result.poll();
if(nowroot.left!=null)
result.add(nowroot.left);
if(nowroot.right!=null)
result.add(nowroot.right);
size = size-1;//
}
height += 1;//高度加1
}
return height;
}
}
4 二叉树任意两个节点之间路径的最大长度
考察点：树
int maxDist(Tree root) {
//如果树是空的，则返回0
if(root == NULL)
return 0;
if(root->left != NULL) {
root->lm = maxDist(root->left) +1;
}
if(root->right != NULL)
root->rm = maxDist(root->right) +1;
//如果以该节点为根的子树中有最大的距离，那就更新最大距离
int sum = root->rm + root->lm;
if(sum > max) {
max = sum;
}
return root->rm > root->lm ?root->rm : root->lm;
}
5 算法题：二叉树层序遍历，进一步提问：要求每层打印出一个换行符
考察点：二叉树
public
List<List<Integer>> levelOrder(TreeNode root) {
// 存最终结果
List<List<Integer>> result = new ArrayList<List<Integer>>();
// 队列
Queue<TreeNode> queue = new LinkedList<TreeNode>();
if (root == null) {
return result;
}
queue.offer(root);
// 层次遍历
while (queue.size() != 0) {
List<Integer> temp = new ArrayList<Integer>();
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode temp = queue.poll();
temp.add(temp.val);
// 左右子树是否为空
if (temp.left != null) {
queue.offer(temp.left);
}
if (temp.right != null) {
queue.offer(temp.right);
}
}
result.add(temp);
}
return result;
}
6 怎么求一个二叉树的深度?手撕代码?
考察点：二叉树
类似上面求二叉树的深度的题，这里给出递归的方式。
public class Solution {
public int TreeDepth(TreeNode root) {
if(root==null)
return 0;
int left = TreeDepth(root.left);
int right = TreeDepth(root.right);
return (left>right)?(left+1):(right+1);
}
}
7 请你说一下，B+树和B-树？
考察点：树
参考回答：
B+树内节点不存储数据，所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而B-树查询时间复杂度不固定，与 key 在树中的位置有关，最好为O(1)。
B+树叶节点两两相连可大大增加区间访问性，可使用在范围查询等，而B-树每个节点 key 和 data 在一起，则无法区间查找。
B+树更适合外部存储。由于内节点无 data 域，每个节点能索引的范围更大更精确。
欢迎大家加我微信交流讨论（请备注csdn上添加）
