啃透二叉树：一线大厂高频面试题精讲与避坑指南

二叉树作为数据结构中的重要组成部分，在面试中占据着举足轻重的地位。无论是算法题还是系统设计题，都可能涉及到二叉树的应用。本文将深入剖析二叉树的高频面试题，从原理到代码，助你彻底掌握二叉树，轻松应对面试挑战。相信通过对二叉树相关知识点的学习，能够让你在面对复杂算法时，更能利用二叉树这种数据结构的特性去巧妙解决。

1. 二叉树的遍历：前序、中序、后序、层序

二叉树的遍历是基础，也是面试常考点。你需要熟练掌握递归和非递归两种实现方式。

**问题场景：**给定一个二叉树，分别用前序、中序、后序、层序遍历输出节点值。

底层原理：

• 前序遍历 (Preorder Traversal): 根节点 -> 左子树 -> 右子树
• 中序遍历 (Inorder Traversal): 左子树 -> 根节点 -> 右子树
• 后序遍历 (Postorder Traversal): 左子树 -> 右子树 -> 根节点
• 层序遍历 (Level Order Traversal): 从上到下，从左到右逐层遍历

代码示例 (Java):

// 前序遍历 (递归)
public void preorderTraversalRecursive(TreeNode root, List<Integer> result) {
    if (root == null) {
        return;
    }
    result.add(root.val); // 先访问根节点
    preorderTraversalRecursive(root.left, result); // 再访问左子树
    preorderTraversalRecursive(root.right, result); // 最后访问右子树
}

// 中序遍历 (非递归)
public List<Integer> inorderTraversalIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;  // 一直找到最左边的节点
        }
        curr = stack.pop();
        result.add(curr.val);  // 访问根节点
        curr = curr.right; // 访问右子树
    }
    return result;
}

// 层序遍历 (广度优先搜索)
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;
}

实战避坑：

• 非递归遍历需要借助栈 (Stack) 数据结构，理解栈的特性非常重要。
• 层序遍历需要借助队列 (Queue) 数据结构，掌握队列的先进先出原则。
• 要注意空指针异常 (NullPointerException) 的处理。

2. 二叉树的深度和高度

二叉树的深度和高度是二叉树的重要属性，经常出现在面试题中。

**问题场景：**给定一个二叉树，求其最大深度和最小深度。

底层原理：

• **深度：**从根节点到该节点的最长简单路径上的边数。
• **高度：**从该节点到叶子节点的最长简单路径上的边数。

通常，我们求二叉树的深度时，默认求的是最大深度。

代码示例 (Python):

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxDepth(root: TreeNode) -> int:
    if not root:
        return 0
    left_depth = maxDepth(root.left)
    right_depth = maxDepth(root.right)
    return max(left_depth, right_depth) + 1

def minDepth(root: TreeNode) -> int:
    if not root:
        return 0
    if not root.left and not root.right:  # 叶子节点
        return 1
    min_d = float('inf')
    if root.left:
        min_d = min(minDepth(root.left), min_d)
    if root.right:
        min_d = min(minDepth(root.right), min_d)
    return min_d + 1

实战避坑：

• 最小深度需要特别注意，当一个节点只有左子树或只有右子树时，不能直接返回 1，需要递归计算左右子树的最小深度。
• 要理解递归的本质，每次递归调用都相当于解决一个规模更小的子问题。

3. 平衡二叉树 (AVL 树)

平衡二叉树是一种特殊的二叉搜索树，它的左右子树的高度差不超过 1。在面试中，可能会考察平衡二叉树的性质和判断方法。

**问题场景：**给定一个二叉树，判断它是否是平衡二叉树。

底层原理：

• 对于树中的每个节点，其左子树和右子树的高度差不能超过 1。
• 可以采用递归的方式，自底向上判断每个节点是否满足平衡二叉树的定义。

**代码示例 (C++): **

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

int getHeight(TreeNode* node) {
    if (node == nullptr) {
        return 0;
    }
    return std::max(getHeight(node->left), getHeight(node->right)) + 1;
}

bool isBalanced(TreeNode* root) {
    if (root == nullptr) {
        return true;
    }
    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);
    if (std::abs(leftHeight - rightHeight) > 1) {
        return false;
    }
    return isBalanced(root->left) && isBalanced(root->right);
}

实战避坑：

• 理解平衡二叉树的定义，高度差不超过 1 是关键。
• 递归判断时，需要同时判断当前节点和其所有子节点是否满足平衡条件。
• 考虑时间复杂度，可以采用自底向上的方式，避免重复计算子树的高度。

4. 二叉搜索树 (BST)

二叉搜索树是一种特殊的二叉树，它的左子树的所有节点值都小于根节点值，右子树的所有节点值都大于根节点值。二叉搜索树在查找、插入、删除等操作上具有较高的效率。

**问题场景：**给定一个二叉搜索树，查找一个节点，插入一个节点，删除一个节点。

底层原理：

• **查找：**从根节点开始，如果目标值小于根节点值，则在左子树中查找；如果目标值大于根节点值，则在右子树中查找；如果目标值等于根节点值，则查找成功。
• **插入：**从根节点开始，找到合适的插入位置（即目标节点应该插入的位置），将新节点插入到该位置。
• **删除：**分为三种情况：删除叶子节点、删除只有一个子节点的节点、删除有两个子节点的节点。对于删除有两个子节点的节点，通常采用中序后继节点或中序前驱节点来替代被删除节点。

**代码示例 (JavaScript): **

class TreeNode {
    constructor(val, left, right) {
        this.val = (val===undefined ? 0 : val)
        this.left = (left===undefined ? null : left)
        this.right = (right===undefined ? null : right)
    }
}

// 查找
function searchBST(root, val) {
    if (!root) return null;
    if (val < root.val) return searchBST(root.left, val);
    if (val > root.val) return searchBST(root.right, val);
    return root;
}

// 插入
function insertIntoBST(root, val) {
    if (!root) return new TreeNode(val);
    if (val < root.val) {
        root.left = insertIntoBST(root.left, val);
    } else {
        root.right = insertIntoBST(root.right, val);
    }
    return root;
}

// 删除
function deleteNode(root, key) {
    if (!root) return null;

    if (key < root.val) {
        root.left = deleteNode(root.left, key);
    } else if (key > root.val) {
        root.right = deleteNode(root.right, key);
    } else { // key === root.val
        // case 1: leaf node
        if (!root.left && !root.right) {
            return null;
        }
        // case 2: one child
        else if (!root.left) {
            return root.right;
        }
        else if (!root.right) {
            return root.left;
        }
        // case 3: two children
        else {
            let minNode = findMin(root.right); // find inorder successor
            root.val = minNode.val;
            root.right = deleteNode(root.right, minNode.val);
        }
    }
    return root;
}

function findMin(node) {
  while (node.left) {
    node = node.left;
  }
  return node;
}

实战避坑：

• 删除节点是二叉搜索树中最复杂的操作，需要考虑多种情况。
• 理解二叉搜索树的性质，可以有效地优化查找、插入、删除等操作。
• 在插入和删除操作后，要保持二叉搜索树的性质。

5. 总结与展望

掌握二叉树的相关知识点，是成为一名优秀的后端工程师的必备技能。在面试中，二叉树问题不仅考察你的算法能力，还考察你的逻辑思维能力和问题解决能力。希望本文能够帮助你更好地理解二叉树，并在面试中取得优异的成绩。另外，二叉树的一些变种，比如红黑树，B树，在数据库和文件系统中应用广泛， 也是深入学习的方向。