Java数据结构-树的面试题

一.谈谈树的种类

二.红黑树如何实现

三.二叉树的题目

1.求一个二叉树的高度，有两种方法。

2.寻找二叉搜索树当中第K大的值

3、查找与根节点距离K的节点

4.二叉树两个结点的公共最近公共祖先

本专栏全是博主自己收集的面试题，仅可参考，不能相信面试官就出这种题目。

一.谈谈树的种类

树，最为常见的是二叉树，而在二叉树的基础上，又衍生了很多具有特性的二叉树。

1.二叉树

每个结点最多有两个子节点，为左节点和右节点

2.二叉搜索树

一种特殊的二叉树，左子树的节点值一定小于右子树的节点值，右子树的节点都大于根节点的值。

3.平衡二叉树

一种特殊的二叉树，也称AVL树，左右子树高度差不超过1。

4.红黑树

特殊的二叉搜索树，名平衡的二叉搜索树（平衡是指，结构稳定），通过节点的颜色保持平衡。根节点是黑色，空节点为黑色，从任一节点到其每个叶子节点的所有路径上不能有两个连续的红色节点，任一节点到其每个叶子节点的路径都包含相同数目的黑色节点。

5.B树和B+树

B树是一种平衡的多路搜索树，广泛用于数据库和文件系统当中，和二叉树不同。

特点：

每个节点可以有多个子节点。
节点中的键值按顺序排列，使得范围查询等操作更加高效。
所有叶子节点都在同一层级，这保证了查找操作的稳定性能。
内部节点存储键值和指向子节点的指针，叶子节点存储键值和实际数据的指针。

B+树与B树的结构很相似，是在B树基础上进行的扩展和优化，也是一种自平衡的树结构，B+树经常用于数据库的索引结构，不同处：

所有的数据都存储在叶子节点中，而非像B树那样部分数据存储在内部节点。并且以链表的形式存在。
由于所有数据都存储在叶子节点且有序排列，B+树支持高效的范围查询（Range Query）和顺序访问。
B+树的内部节点只存储键值和指向子节点的指针，而叶子节点之间通过链表连接，这样的结构使得范围查询更为高效。

6.Trie树

一种树形结构，典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串,如01字典树）。主要思想是利用字符串的公共前缀来节约存储空间。很好地利用了串的公共前缀，节约了存储空间。字典树主要包含两种操作，插入和查找。

7.堆

堆是一种结构类似树形结构，通常实现优先队列，有最大堆和最小堆两种形式。

二.红黑树如何实现

节点结构：每个节点包含关键字（key)，颜色（红或黑），指向左子节点和右子节点的指针，以及指向父节点的指针。叶子节点通常被视为NIL节点，它们是黑色的。

颜色规则：根节点为黑色，叶子节点都是黑色，一个节点是红色，那么子节点为黑色。

路径规则：任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点，最短路径和最长路径不会相差超过2倍。

插入规则：插入节点默认为红色，

插入结点是根节点，直接变黑
插入结点的叔叔是红色，叔父爷结点都变色，爷爷变插入结点
插入结点的叔叔是黑色，判断（LL,RR,LR,RL）进行旋转，然后变色。

删除规则：

讲不清楚，可以去看B站红黑树讲解：https://www.bilibili.com/

三.二叉树的题目

1.求一个二叉树的高度，有两种方法。

第一种是递归；第二种是迭代。

// 求二叉树高度的函数
public class BinaryTreeHeight {

    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int leftHeight = getHeight(root.left);
            int rightHeight = getHeight(root.right);

            // 返回左右子树中较大的高度，并加上根节点的高度1
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
    //层序遍历
    public int getHeight2(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int height = 0;

        while (!queue.isEmpty()) {
            int levelSize = queue.size(); // 当前层的节点数量

            // 遍历当前层的所有节点，并将它们的子节点加入队列
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            // 每遍历完一层，高度加一
            height++;
        }

        return height;
    }
    public static void main(String[] args) {
        // 创建一个示例二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        // 计算二叉树的高度
        BinaryTreeHeight btHeight = new BinaryTreeHeight();
        int height = btHeight.getHeight(root);
        System.out.println("Binary Tree Height: " + height); // 输出高度
    }
}

2.寻找二叉搜索树当中第K大的值

思路：二叉搜索树（BST）的后序遍历实际是对树节点的升序排列。所以同第一题，有递归法和迭代法实现BST的中序遍历，遍历后再逆序，返回第k个最大值。

递归法实现中序遍历：中序遍历，可以得到二叉搜索树从小到大排序，那么逆中序遍历，并且设置一个变量result，每一次遍历，都增一，当result等于K时，则得出结果！

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class KthLargestInBST {

    private int count;
    private int result;

    public int kthLargest(TreeNode root, int k) {
        count = 0;
        result = 0;
        reverseInOrder(root, k);
        return result;
    }

    private void reverseInOrder(TreeNode node, int k) {
        if (node == null || count >= k) {
            return;
        }
        
        // 递归右子树
        reverseInOrder(node.right, k);
        
        // 访问当前节点
        count++;
        if (count == k) {
            result = node.val;
            return; // 提前结束递归
        }
        
        // 递归左子树
        reverseInOrder(node.left, k);
    }

    public static void main(String[] args) {
        // 创建一个示例二叉搜索树
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(10);

        int k = 3; // 寻找第三大的值
        KthLargestInBST solution = new KthLargestInBST();
        int kthLargest = solution.kthLargest(root, k);
        System.out.println("The " + k + "th largest element in BST is: " + kthLargest); // 输出结果
    }
}

3、查找与根节点距离K的节点

直接深度优先遍历（DFS）或者广度优先遍历（BFS）

广度优先搜索（BFS）+队列：我们可以在遍历每一层节点时，将该节点的子节点加入队列（size--控制循环），并记录它们的距离。当距离等于K时，将该节点的值存储起来。

深度优先搜索（DFS）+栈：使用一个栈来存储当前节点和距离的信息。在每次循环中，取出栈顶元素，检查当前距离是否等于K，如果是，则将该节点的值存储到结果数组中。然后，将当前节点的子节点按照右子节点先入栈，左子节点后入栈，并将距离加1。这样，我们可以确保在深度优先搜索中，离根节点更远的节点会在栈中先被访问。

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int x) {
        val = x;
    }
}

public class NodesAtDistanceK {

    public List<Integer> findNodesAtDistanceK(TreeNode root, int K) {
        List<Integer> result = new ArrayList<>();
        findNodesAtDistanceK(root, K, result);
        return result;
    }

    private int findNodesAtDistanceK(TreeNode node, int K, List<Integer> result) {
        if (node == null) return -1; // 如果节点为空，返回 -1 表示找不到目标距离 K 的节点
        
        if (K == 0) {
            result.add(node.val); // 当 K 为 0，说明当前节点就是目标节点
            return 0;
        }
        
        // 递归左子树，在左子树中查找距离 K 的节点
        int leftDistance = findNodesAtDistanceK(node.left, K - 1, result);
        if (leftDistance != -1) {
            // 如果找到目标节点，当前节点距离根节点的距离就是 leftDistance + 1
            if (leftDistance + 1 == K) {
                result.add(node.val);
            } else {
                // 否则，继续在右子树中查找剩余距离的节点
                findNodesAtDistanceK(node.right, K - leftDistance - 2, result);
            }
            return leftDistance + 1; // 返回左子树中目标距离 K 的节点距离
        }
        
        // 递归右子树，在右子树中查找距离 K 的节点
        int rightDistance = findNodesAtDistanceK(node.right, K - 1, result);
        if (rightDistance != -1) {
            // 如果找到目标节点，当前节点距离根节点的距离就是 rightDistance + 1
            if (rightDistance + 1 == K) {
                result.add(node.val);
            } else {
                // 否则，继续在左子树中查找剩余距离的节点
                findNodesAtDistanceK(node.left, K - rightDistance - 2, result);
            }
            return rightDistance + 1; // 返回右子树中目标距离 K 的节点距离
        }
        
        return -1; // 如果左右子树都找不到目标距离 K 的节点，返回 -1
    }

    public static void main(String[] args) {
        // 创建示例二叉树
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);

        NodesAtDistanceK solution = new NodesAtDistanceK();
        int K = 2;
        List<Integer> nodesAtDistanceK = solution.findNodesAtDistanceK(root, K);
        System.out.println("Nodes at distance " + K + " from root: " + nodesAtDistanceK);
    }
}

4.二叉树两个结点的公共最近公共祖先

思路：使用递归。

方法一：假设，如上图的二叉树，我们需要查出2，0的最近公共祖先，我们可以通过后序遍历搭配栈使用，得出从根节点到2的路径 3->5->2 和从根结点到0的路径 3->1->0 通过路径相比，我们可以得出3是他们最近的公共结点

方法二：从根节点开始递归搜索：

如果当前节点是 null，或者等于 p 或 q，则直接返回当前节点。
递归地在左子树和右子树中搜索节点 p 和节点 q。

根据左右子树的搜索结果，判断以下几种情况：

如果左子树和右子树分别找到了 p 和 q，说明当前节点就是它们的最近公共祖先。
如果只在左子树找到了 p 或 q，则说明公共祖先必定在左子树。
如果只在右子树找到了 p 或 q，则说明公共祖先必定在右子树。

public class LowestCommonAncestor {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 如果根节点为空，直接返回null
        if (root == null) return null;
        
        // 如果根节点是其中一个目标节点，直接返回根节点
        if (root == p || root == q) return root;
        
        // 在左子树中查找p和q的最近公共祖先
        TreeNode leftLCA = lowestCommonAncestor(root.left, p, q);
        // 在右子树中查找p和q的最近公共祖先
        TreeNode rightLCA = lowestCommonAncestor(root.right, p, q);
        
        // 如果左右子树分别找到了p和q，则当前节点是最近公共祖先
        if (leftLCA != null && rightLCA != null) {
            return root;
        }
        
        // 如果只有一边找到了最近公共祖先，则返回那个节点
        return (leftLCA != null) ? leftLCA : rightLCA;
    }

    public static void main(String[] args) {
        // 创建示例二叉树
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);

        LowestCommonAncestor solution = new LowestCommonAncestor();
        TreeNode p = root.left.left;
        TreeNode q = root.left.right.left;
        TreeNode lca = solution.lowestCommonAncestor(root, p, q);
        
        System.out.println("Lowest Common Ancestor of " + p.val + " and " + q.val + " is: " + lca.val);
    }
}