剑指Offer：二叉树高频面试题精讲与实战演练

二叉树作为一种重要的数据结构，在算法面试中占据着举足轻重的地位。很多候选人在面对二叉树相关问题时，常常感到束手无策。本文将深入剖析二叉树 数据结构 的高频热门面试题，从底层原理到代码实现，助你彻底掌握二叉树的精髓，顺利通过面试。

二叉树基础回顾：概念、性质与遍历方式

在深入探讨面试题之前，我们先来回顾一下二叉树的基本概念和性质：

• 二叉树的定义：每个节点最多只有两个子节点（左子节点和右子节点）的树结构。
• 二叉树的类型：
  • 满二叉树：所有层级的节点都是最大数量。
  • 完全二叉树：除了最后一层，其他层级的节点都是最大数量，并且最后一层的节点都集中在左侧。
  • 平衡二叉树 (AVL树)： 左右子树的高度差不超过1。
• 二叉树的遍历方式：
  • 前序遍历（Preorder Traversal）：根节点 -> 左子树 -> 右子树
  • 中序遍历（Inorder Traversal）：左子树 -> 根节点 -> 右子树
  • 后序遍历（Postorder Traversal）：左子树 -> 右子树 -> 根节点
  • 层序遍历（Level Order Traversal）：逐层从左到右遍历

代码示例：二叉树的遍历（递归实现）

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

public class BinaryTreeTraversal {

    // 前序遍历
    public void preorderTraversal(TreeNode root) {
        if (root == null) return;
        System.out.print(root.val + " "); // 输出根节点
        preorderTraversal(root.left);   // 递归遍历左子树
        preorderTraversal(root.right);  // 递归遍历右子树
    }

    // 中序遍历
    public void inorderTraversal(TreeNode root) {
        if (root == null) return;
        inorderTraversal(root.left);    // 递归遍历左子树
        System.out.print(root.val + " "); // 输出根节点
        inorderTraversal(root.right);   // 递归遍历右子树
    }

    // 后序遍历
    public void postorderTraversal(TreeNode root) {
        if (root == null) return;
        postorderTraversal(root.left);    // 递归遍历左子树
        postorderTraversal(root.right);   // 递归遍历右子树
        System.out.print(root.val + " "); // 输出根节点
    }

    // 层序遍历 (使用队列实现)
    public void levelOrderTraversal(TreeNode root) {
        if (root == null) return;

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

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.val + " ");

            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

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

        BinaryTreeTraversal traversal = new BinaryTreeTraversal();

        System.out.print("前序遍历：");
        traversal.preorderTraversal(root);
        System.out.println();

        System.out.print("中序遍历：");
        traversal.inorderTraversal(root);
        System.out.println();

        System.out.print("后序遍历：");
        traversal.postorderTraversal(root);
        System.out.println();

        System.out.print("层序遍历：");
        traversal.levelOrderTraversal(root);
        System.out.println();
    }
}

高频面试题精讲

1. 二叉树的最大深度

问题描述：给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

解题思路：可以使用递归的方式解决。二叉树的最大深度等于其左右子树的最大深度加 1。

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftDepth = maxDepth(root.left);  // 递归计算左子树的深度
    int rightDepth = maxDepth(root.right); // 递归计算右子树的深度
    return Math.max(leftDepth, rightDepth) + 1; // 返回左右子树深度最大值 + 1
}

2. 判断二叉树是否对称

问题描述：给定一个二叉树，检查它是否是镜像对称的。

解题思路：递归判断左右子树是否镜像对称。如果两个节点的值相等，并且它们的左右子节点分别镜像对称，则这两个节点是对称的。

public boolean isSymmetric(TreeNode root) {
    return isMirror(root, root);
}

private boolean isMirror(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null) return true;  // 两个节点都为空，对称
    if (t1 == null || t2 == null) return false; // 只有一个节点为空，不对称
    return (t1.val == t2.val)
            && isMirror(t1.right, t2.left)  // 递归判断 t1 的右子树和 t2 的左子树是否对称
            && isMirror(t1.left, t2.right);  // 递归判断 t1 的左子树和 t2 的右子树是否对称
}

3. 二叉树的最近公共祖先

问题描述：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

解题思路：

• 如果 root 为空，或者 root 等于 p 或 q，则 root 为最近公共祖先。
• 递归查找 p 和 q 在 root 的左右子树中。
• 如果 p 和 q 分别在左右子树中，则 root 为最近公共祖先。
• 如果 p 和 q 都在左子树中，则最近公共祖先在左子树中。
• 如果 p 和 q 都在右子树中，则最近公共祖先在右子树中。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) {
        return root;
    }

    TreeNode left = lowestCommonAncestor(root.left, p, q);   // 递归查找左子树
    TreeNode right = lowestCommonAncestor(root.right, p, q);  // 递归查找右子树

    if (left != null && right != null) {
        return root; // p 和 q 分别在左右子树中，root 是最近公共祖先
    } else if (left != null) {
        return left; // p 和 q 都在左子树中，最近公共祖先在左子树中
    } else {
        return right; // p 和 q 都在右子树中，最近公共祖先在右子树中
    }
}

4. 二叉树的序列化与反序列化

问题描述：设计一个算法来实现二叉树的序列化与反序列化。序列化是将一个数据结构或者对象转换为一系列位的过程，以便它可以存储在文件或者内存缓冲区中，或者通过网络连接链路传输，以便稍后在同一个或者另一个计算机环境中重构。

解题思路：

• 序列化：使用前序遍历，将节点的值按照 “值,” 的格式拼接成字符串。空节点用 “#,” 表示。
• 反序列化：将序列化后的字符串按照 “,” 分割成数组。然后，递归地构建二叉树。

public class Codec {
    private static final String NULL = "#";
    private static final String SEP = ",";

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serializeHelper(root, sb);
        return sb.toString();
    }

    private void serializeHelper(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append(NULL).append(SEP); // 空节点用 # 表示
            return;
        }

        sb.append(root.val).append(SEP); // 添加节点值
        serializeHelper(root.left, sb);  // 递归序列化左子树
        serializeHelper(root.right, sb); // 递归序列化右子树
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        Queue<String> nodes = new LinkedList<>(Arrays.asList(data.split(SEP)));
        return deserializeHelper(nodes);
    }

    private TreeNode deserializeHelper(Queue<String> nodes) {
        String val = nodes.poll();
        if (val.equals(NULL)) {
            return null; // 遇到 #，表示空节点
        }

        TreeNode root = new TreeNode(Integer.parseInt(val)); // 创建节点
        root.left = deserializeHelper(nodes);  // 递归反序列化左子树
        root.right = deserializeHelper(nodes); // 递归反序列化右子树
        return root;
    }
}

实战避坑经验总结

1. 注意空指针异常：在处理二叉树问题时，务必注意判断节点是否为空，避免空指针异常。
2. 理解递归的本质：很多二叉树问题都可以使用递归解决，要理解递归的本质，掌握递归的写法。
3. 熟练掌握遍历方式：熟练掌握二叉树的各种遍历方式，可以帮助你更好地理解和解决二叉树问题。
4. 多练习：通过大量的练习，才能真正掌握二叉树的精髓。

希望以上分析能够帮助你更好地掌握二叉树 数据结构，在面试中脱颖而出！别忘了在项目中灵活应用这些知识，例如构建高性能的索引结构或实现高效的数据搜索算法。此外，对于高并发场景，可以考虑结合 Nginx 等负载均衡工具，提升系统的稳定性和可用性。 在 Nginx 配置中，可以使用 upstream 模块进行服务器集群的管理，通过反向代理将请求分发到不同的后端服务器，有效应对高并发请求。