Java工程师 数据结构与算法 树面试题(Day37)

  • 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上添加)
Java工程师 数据结构与算法 树面试题(Day37)

w3cjava