剑指 Offer：二叉树高频面试题精讲与解法

内容摘要：剑指 Offer：二叉树高频面试题精讲与解法,

二叉树作为一种重要的数据结构，在面试中经常出现。本文将从一名拥有 10 年经验的后端架构师的角度，深入剖析二叉树的常见面试题，帮助你掌握二叉树的核心概念和解题技巧。本文侧重讲解二叉树【数据结构】相关的高频热门面试题。

1. 二叉树的遍历

二叉树的遍历是所有二叉树问题的基础，包括前序遍历、中序遍历、后序遍历和层序遍历。掌握各种遍历方式的递归和非递归实现是必须的。

1.1 前序遍历（Preorder Traversal）

先访问根节点，然后访问左子树，最后访问右子树。

递归实现：

public void preorderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    System.out.println(root.val); // 访问根节点
    preorderTraversal(root.left);   // 递归遍历左子树
    preorderTraversal(root.right);  // 递归遍历右子树
}

非递归实现（使用栈）：

public List<Integer> preorderTraversalIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
    return result;
}

1.2 中序遍历（Inorder Traversal）

先访问左子树，然后访问根节点，最后访问右子树。

递归实现：

public void inorderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    inorderTraversal(root.left);   // 递归遍历左子树
    System.out.println(root.val); // 访问根节点
    inorderTraversal(root.right);  // 递归遍历右子树
}

非递归实现（使用栈）：

public List<Integer> inorderTraversalIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;

    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        result.add(current.val);
        current = current.right;
    }
    return result;
}

1.3 后序遍历（Postorder Traversal）

先访问左子树，然后访问右子树，最后访问根节点。

递归实现：

public void postorderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    postorderTraversal(root.left);   // 递归遍历左子树
    postorderTraversal(root.right);  // 递归遍历右子树
    System.out.println(root.val); // 访问根节点
}

非递归实现（使用栈）： 后序遍历的非递归实现比较复杂，需要使用两个栈或者标记节点是否被访问过。

1.4 层序遍历（Level Order Traversal）

逐层从左到右访问节点。通常使用队列来实现。

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

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

    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        result.add(level);
    }
    return result;
}

2. 常见面试题

2.1 翻转二叉树

将二叉树的每个节点的左右子树交换。

public TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    invertTree(root.left);
    invertTree(root.right);
    return root;
}

2.2 判断是否为平衡二叉树

平衡二叉树是指任意节点的左右子树的高度差不超过 1。

public boolean isBalanced(TreeNode root) {
    return height(root) != -1;
}

private int height(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftHeight = height(root.left);
    if (leftHeight == -1) {
        return -1;
    }
    int rightHeight = height(root.right);
    if (rightHeight == -1) {
        return -1;
    }
    if (Math.abs(leftHeight - rightHeight) > 1) {
        return -1;
    }
    return Math.max(leftHeight, rightHeight) + 1;
}

2.3 二叉树的最大深度

二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

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

2.4 寻找二叉树的最近公共祖先 (LCA)

给定二叉树中的两个节点，找到它们的最近公共祖先。

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;
    }
    return left != null ? left : right;
}

3. 实战避坑经验

• 空指针检查： 在访问二叉树节点之前，务必进行空指针检查，避免 NullPointerException。
• 递归深度： 递归实现二叉树算法时，要注意递归深度，防止栈溢出。可以使用尾递归优化或者迭代实现来避免。
• 边界条件： 考虑边界条件，例如空树、单节点树等，确保算法的正确性。
• 时间复杂度： 分析算法的时间复杂度，选择最优的解决方案。例如，平衡二叉树的查找效率比普通二叉树更高。

掌握这些二叉树的【数据结构】相关面试题和解题技巧，相信你能在面试中脱颖而出。希望这篇文章能帮助你更好地理解二叉树，并在面试中取得成功。