企业官网建设流程全解析

前言

二叉树是数据结构与算法面试和笔试中的高频考点，也是许多复杂算法（如二叉搜索树、堆、AVL树等）的基础。掌握二叉树的常见OJ（Online Judge）题目，对于提升编程能力和算法思维至关重要。本文将系统梳理二叉树的核心OJ题型，并提供清晰的解题思路和代码示例（以C为主），帮助你从原理到实战，彻底攻破二叉树难题。

一、高频OJ题型分类与攻破

1.单值二叉树

解题思路：单值二叉树的判断核心是递归遍历。从根节点开始，检查当前节点的值是否与左右子节点相同（如果子节点存在）。递归检查左右子树是否也都是单值二叉树。时间复杂度 O(n)，空间复杂度 O(h)，其中 h 为树高。

关键知识点：

• 递归终止条件：空树视为单值二叉树（返回 true）
• 递归逻辑：先检查当前节点与子节点的值是否一致，再递归检查左右子树
• 边界处理：注意子节点可能为 NULL 的情况，避免空指针访问
• 递归返回值：使用逻辑与（&&）连接左右子树的检查结果

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool isUnivalTree(struct TreeNode* root) { if(root == NULL) return true; if(root->left && root->left->val != root->val) return false; if(root->right && root->right->val != root->val) return false; return isUnivalTree(root->left) && isUnivalTree(root->right); }

2. 对称二叉树

解题思路：对称二叉树的判断需要比较左右子树是否镜像对称。通过递归比较左子树的左节点与右子树的右节点，以及左子树的右节点与右子树的左节点。时间复杂度 O(n)，空间复杂度 O(h)，其中 h 为树高。

关键知识点：

• 递归逻辑：比较当前节点的值，然后递归比较左子树的左节点与右子树的右节点，以及左子树的右节点与右子树的左节点
• 镜像对称：对称二叉树要求左右子树镜像对称

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool ismirrortree(struct TreeNode* p,struct TreeNode* q) { if(p == NULL && q == NULL) return true; else if(p == NULL || q == NULL) return false; else if(p->val != q->val) return false; return ismirrortree(p->left,q->right) && ismirrortree(p->right,q->left); } bool checkSymmetricTree(struct TreeNode* root) { if(root == NULL) return true; return ismirrortree(root->left,root->right); }

3. 另一颗树的子树

解题思路：判断一棵树是否是另一棵树的子树，需要遍历主树的每个节点，检查以该节点为根的子树是否与目标子树完全相同。通过递归遍历主树，对每个节点调用判断两棵树是否相同的函数。时间复杂度 O(m×n)，其中 m 和 n 分别是两棵树的节点数。

关键知识点：

• 双重递归：外层递归遍历主树的每个节点，内层递归判断两棵树是否相同
• 相同树判断：需要先实现判断两棵树是否完全相同的函数
• 逻辑或连接：当前节点开始的子树相同，或者左子树包含目标子树，或者右子树包含目标子树

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool issametree(struct TreeNode* p, struct TreeNode* q) { if(p == NULL && q == NULL) return true; if(p == NULL || q == NULL) return false; if(p->val != q->val) return false; return issametree(p->left,q->left) && issametree(p->right,q->right); } bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) { if(root == NULL) return false; if(subRoot == NULL) return true; return issametree(root,subRoot) || isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot); }

4.通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树

解题思路：通过前序遍历数组构建二叉树，其中 '#' 表示空节点。使用递归方法，每次读取一个字符：如果是 '#' 则返回 NULL；否则创建新节点，递归构建左子树和右子树。需要传递索引指针来跟踪当前读取位置。

关键知识点：

• 前序遍历顺序：根节点 → 左子树 → 右子树
• 空节点表示：通常用特殊字符（如 '#'）表示空节点
• 索引传递：需要使用指针传递索引，确保递归过程中索引正确递增
• 递归构建：先创建根节点，然后递归构建左子树，最后递归构建右子树
• 内存分配：为每个非空节点动态分配内存，注意检查分配是否成功

BTNode* BinaryTreeCreate(char* a, int* pi) { if(a[(*pi)]== '#') { *(pi)++; return NULL; } BTNode* root = (BTNode*)malloc(sizeof(BTNode)); root->val = a[(*pi)++]; root->left = BinaryTreeCreate(a,pi); root->right = BinaryTreeCreate(a,pi); return root; }

5.判断二叉树是否是完全二叉树

解题思路：判断完全二叉树使用层序遍历（队列实现）。将根节点入队，然后循环出队节点，将其左右子节点入队（包括空节点）。当遇到第一个空节点时，停止入队。继续检查队列中剩余节点：如果还有非空节点，则不是完全二叉树。时间复杂度 O(n)，空间复杂度 O(n)。

关键知识点：

• 层序遍历：使用队列进行广度优先遍历
• 完全二叉树定义：除了最后一层，其他层都是满的，且最后一层的节点都靠左排列
• 空节点处理：需要将空节点也入队，用于检测是否出现"空洞"
• 队列实现：需要实现队列的基本操作（初始化、入队、出队、取队首、判空）
• 算法步骤：1. 层序遍历直到遇到第一个空节点；2. 检查队列剩余节点是否全为空

//队列的初始化 void QInit(Que* pst) { assert(pst); pst->phead = pst->ptail = 0; pst->size = 0; } //队尾数据插入 void QPush(Que* pst, QDataType x) { assert(pst); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc failed"); return; } newnode->next = NULL; newnode->data = x; if (pst->phead == NULL) pst->phead = pst->ptail = newnode; else { pst->ptail->next = newnode; pst->ptail = newnode; } pst->size++; } //队头数据删除 void QPop(Que* pst) { assert(pst); if (pst->phead->next == NULL) { free(pst->phead); pst->phead = pst->ptail = NULL; } else { QNode* next = pst->phead->next; free(pst->phead); pst->phead = next; } pst->size--; } //取队顶数据 QDataType QTop(Que* pst) { assert(pst); return pst->phead->data; } //判断队列是否为空 bool QEmpty(Que* pst) { assert(pst); return pst->size == 0; } //手搓一棵二叉树 BT* BTBuyNode(BTDataType x) { BT* newnode = (BT*)malloc(sizeof(BT)); if (newnode == NULL) { perror("malloc failed"); return NULL; } newnode->left = newnode->right = NULL; newnode->data = x; return newnode; } //判断二叉树是否是完全二叉树 bool BinaryTreeComplete(BT* root) { Que queue; QInit(&queue); QPush(&queue, root); while (!QEmpty(&queue)) { BT* cur = QTop(&queue); QPop(&queue); if (cur == NULL) break; QPush(&queue, cur->left); QPush(&queue, cur->right); } while (!QEmpty(&queue)) { BT* cur = QTop(&queue); QPop(&queue); if (cur != NULL) { printf("不是完全二叉树！\n"); return false; } } printf("是完全二叉树！\n"); return true; }

二、总结

攻破二叉树OJ题的关键在于熟练掌握基础遍历，并深刻理解递归与分治的思想。建议按照本文的分类，从易到难逐个击破。每做完一道题，尝试用另一种遍历顺序或迭代方法重写，并总结同类题目的共性。坚持练习，你将对二叉树的结构和操作产生直觉，在面试中游刃有余。