嵌入式大厂面经 二叉树常见面试题（持续更新中！）

这是一个嵌入式大厂面试题专栏，每天更新高频面试题。专栏将包含题目描述、详细解析、相关知识点扩展以及实际代码示例。内容涵盖操作系统、驱动开发、通信协议等核心领域，并结合实际项目经验进行分析。每道题目都会附带面试官可能的追问方向，帮助大家更好地准备面试！

一、基础概念

1. 二叉树的基本定义与实现

// 二叉树节点结构定义
typedef struct TreeNode {
    int data;                // 节点数据
    struct TreeNode *left;   // 左子节点指针
    struct TreeNode *right;  // 右子节点指针
} TreeNode;

// 创建新节点
TreeNode* createNode(int value) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if(newNode == NULL) {
        // 内存分配失败处理
        return NULL;
    }
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

2. 二叉树的特殊类型

• 完全二叉树：除最后一层外，其他层节点数达到最大，且最后一层节点从左到右填充
• 满二叉树：所有层的节点数都达到最大
• 二叉搜索树：左子树所有节点值小于根节点，右子树所有节点值大于根节点
• 平衡二叉树：任意节点的左右子树高度差不超过1

二、遍历算法

1. 深度优先遍历（DFS）

前序遍历（根-左-右）

void preorderTraversal(TreeNode* root) {
    if(root == NULL) return;
    
    printf("%d ", root->data);       // 访问根节点
    preorderTraversal(root->left);   // 遍历左子树
    preorderTraversal(root->right);  // 遍历右子树
}

中序遍历（左-根-右）

void inorderTraversal(TreeNode* root) {
    if(root == NULL) return;
    
    inorderTraversal(root->left);    // 遍历左子树
    printf("%d ", root->data);       // 访问根节点
    inorderTraversal(root->right);   // 遍历右子树
}

后序遍历（左-右-根）

void postorderTraversal(TreeNode* root) {
    if(root == NULL) return;
    
    postorderTraversal(root->left);  // 遍历左子树
    postorderTraversal(root->right); // 遍历右子树
    printf("%d ", root->data);       // 访问根节点
}

2. 非递归实现（栈实现）

前序遍历非递归实现

void preorderIterative(TreeNode* root) {
    if(root == NULL) return;
    
    // 创建栈
    TreeNode* stack[100];  // 假设最多100个节点
    int top = -1;
    
    // 根节点入栈
    stack[++top] = root;
    
    while(top >= 0) {
        // 出栈并访问
        TreeNode* node = stack[top--];
        printf("%d ", node->data);
        
        // 先右后左入栈（出栈时会先处理左节点）
        if(node->right) stack[++top] = node->right;
        if(node->left) stack[++top] = node->left;
    }
}

3. 层序遍历（BFS）

void levelOrderTraversal(TreeNode* root) {
    if(root == NULL) return;
    
    // 创建队列
    TreeNode* queue[100];  // 假设最多100个节点
    int front = 0, rear = 0;
    
    // 根节点入队
    queue[rear++] = root;
    
    while(front < rear) {
        // 出队并访问
        TreeNode* node = queue[front++];
        printf("%d ", node->data);
        
        // 左右子节点入队
        if(node->left) queue[rear++] = node->left;
        if(node->right) queue[rear++] = node->right;
    }
}

三、常见操作与算法

1. 计算二叉树高度

int getHeight(TreeNode* root) {
    if(root == NULL) return 0;
    
    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);
    
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

2. 判断是否为平衡二叉树

int isBalanced(TreeNode* root) {
    if(root == NULL) return 1;  // 空树是平衡的