数据结构：二叉树OJ题攻破

前言二叉树是数据结构与算法面试和笔试中的高频考点也是许多复杂算法如二叉搜索树、堆、AVL树等的基础。掌握二叉树的常见OJOnline 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-gt;phead NULL) pst-gt;phead pst-gt;ptail newnode; else { pst-gt;ptail-gt;next newnode; pst-gt;ptail newnode; } pst-gt;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(amp;queue, root); while (!QEmpty(amp;queue)) { BT* cur QTop(amp;queue); QPop(amp;queue); if (cur NULL) break; QPush(amp;queue, cur-gt;left); QPush(amp;queue, cur-gt;right); } while (!QEmpty(amp;queue)) { BT* cur QTop(amp;queue); QPop(amp;queue); if (cur ! NULL) { printf(不是完全二叉树\n); return false; } } printf(是完全二叉树\n); return true; }二、总结攻破二叉树OJ题的关键在于熟练掌握基础遍历并深刻理解递归与分治的思想。建议按照本文的分类从易到难逐个击破。每做完一道题尝试用另一种遍历顺序或迭代方法重写并总结同类题目的共性。坚持练习你将对二叉树的结构和操作产生直觉在面试中游刃有余。