树

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]
     }
 }

如何打印二叉树每层的节点？

考察点：二叉树

注意：面试中一般写核心代码，另外就是可以问一下面试是输出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;
    }
}

如何知道二叉树的深度？

考察点：二叉树

参考回答：

求二叉树的深度方式有两种，递归以及非递归。(出自剑指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;
    }
}

二叉树任意两个节点之间路径的最大长度

考察点：树

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; 
}

算法题：二叉树层序遍历，进一步提问：要求每层打印出一个换行符

考察点：二叉树

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;
}

怎么求一个二叉树的深度?手撕代码?

考察点：二叉树

类似上面求二叉树的深度的题，这里给出递归的方式。

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);
    }
}

请你说一下，B+树和B-树？

考察点：树

参考回答：

• B+树内节点不存储数据，所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而B-树查询时间复杂度不固定，与 key 在树中的位置有关，最好为O(1)。
• B+树叶节点两两相连可大大增加区间访问性，可使用在范围查询等，而B-树每个节点 key 和 data 在一起，则无法区间查找。
• B+树更适合外部存储。由于内节点无 data 域，每个节点能索引的范围更大更精确

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名，转载请...
最后编辑时间为: 2023/03/01 18:01:43