二叉树专题（一）：从递归判断到子树匹配与遍历建树

写在前面前面的「数据结构——二叉树」系列主要围绕二叉树本身的结构和基础接口展开。从三种递归遍历开始我们已经陆续实现了结点数量、叶子结点数量、树的高度、第 K 层结点数量、层序遍历、结点查找、二叉树销毁、前序序列建树等接口帮助我们逐渐熟悉二叉树最基本的递归模型。但真正开始做题以后会发现知道「二叉树要用递归」和真正能够写对递归还是两件不同的事情。尤其是这些问题递归函数到底代表什么什么时候返回 true什么时候返回 false左右子树的结果该用还是||递归函数返回的结果是否被正确接住同时递归两棵树时两个参数到底应该怎样变化力扣要求返回动态数组时应该如何组织结果。这些问题都需要通过具体题目才能真正掌握。因此从本篇开始进入二叉树专题练习。本篇按照以下路线逐步展开单值二叉树100. 相同的树572. 另一棵树的子树144. 二叉树的前序遍历TSINGK110 二叉树遍历前几题逐步深化递归判断逻辑最后进入遍历结果保存与前序序列建树。一、LeetCode 965单值二叉树1.1 题目如果二叉树每个结点都具有相同的值那么这棵树就是单值二叉树。只有给定的树是单值二叉树时返回true否则返回false。1.2 递归函数的定义对于当前结点root我们需要保证左孩子的值和 root 相同右孩子的值和 root 相同左子树本身也是单值树右子树本身也是单值树因此递归函数isUnivalTree(root)可以定义为判断以 root 为根的整棵树是不是单值二叉树。1.3 递归终止与逐层判断终止条件空树视为合法如果root NULL空树本身不会产生不同值满足单值要求if (root NULL) { return true; }当前层校验左右孩子值匹配左孩子存在时比较值是否相等不等则直接返回 falseif (root-left root-left-val ! root-val) { return false; }右孩子同理if (root-right root-right-val ! root-val) { return false; }这里先判断root-left是为了避免空指针解引用root-left-val。1.4 左右子树必须同时成立当前层检查没有问题以后继续递归校验子树return isUnivalTree(root-left) isUnivalTree(root-right);这里必须用原因很直接左子树是单值树并且右子树也是单值树整棵树才是单值树。1.5 完整代码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); }1.6 题后总结这道题第一次非常清晰地体现了二叉树递归的经典结构当前层条件 左子树结果 右子树结果也就是当前结点合法 左子树合法 右子树合法做二叉树递归题时首先要想清楚左右两棵子树之间到底是什么关系这道题的答案是「必须同时满足」所以使用。这个思想马上会在下一道题中再次出现。二、LeetCode 100相同的树2.1 题目给出两棵二叉树p和q如果两棵树结构完全相同且对应位置的结点值全部相同就认为两棵树相同。2.2 双树同步递归的思路定义递归函数isSameTree(p, q)判断以 p 和 q 为根的两棵二叉树是否完全相同。和上一题不同这里需要同时观察两个结点两棵树同步向下递归。2.3 三种边界情况情况1两个结点都为空if (p NULL q NULL) { return true; }两个位置结构一致返回 true。情况2一个为空一个不为空if (p NULL || q NULL) { return false; }注意这里是在已经排除「两者都为空」之后判断只要有一个为空就说明结构不一样。情况3值不同两个结点都存在时比较值if (p-val ! q-val) { return false; }结构位置一致但值不同仍然不是相同的树。2.4 左右子树必须同时相同当前根结点相同还不够还必须保证p 的左子树 q 的左子树p 的右子树 q 的右子树因此return isSameTree(p-left, q-left) isSameTree(p-right, q-right);这里再次出现了和上一题类似的A B结构。2.5 完整代码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); }2.6 题后总结回头对比单值二叉树和相同的树单值二叉树return isUnivalTree(root-left) isUnivalTree(root-right);相同的树return isSameTree(p-left, q-left) isSameTree(p-right, q-right);写法不同但思维模式完全一致当前层满足要求以后整棵树是否满足条件由左右子树共同决定。也正是完成「相同的树」以后下一题「另一棵树的子树」就自然出现了。三、LeetCode 572另一棵树的子树3.1 题目给出两棵树root和subRoot判断 root 中是否存在某一个结点使以这个结点为根的整棵子树与 subRoot 完全相同。3.2 两层递归的拆解这道题实际上包含两个问题两棵树是否相同—— 这正是刚刚写完的isSameTreeroot 的哪个位置可能和 subRoot 相同—— 遍历 root 的所有结点因此 572 很适合直接复用 100 的代码形成「外层遍历 内层匹配」的两层递归。站在当前 root 位置上先判断isSameTree(root, subRoot)如果相同直接返回 true如果当前位置不匹配那么还有两个可能subRoot 出现在 root 的左子树中或者出现在右子树中。只要其中一个存在即可因此用||连接。return isSubtree(root-left, subRoot) || isSubtree(root-right, subRoot);3.3 完整代码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; } // 先判断以当前 root 为根的树是否和 subRoot 相同 if (isSameTree(root, subRoot)) { return true; } // 当前位置不相同再去 root 的左右子树寻找 return isSubtree(root-left, subRoot) || isSubtree(root-right, subRoot); }3.4 典型错误复盘我第一次写这道题时写出了下面这种结构踩了三个非常典型的递归坑bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) { if (root NULL subRoot NULL) { return true; } if (isSameTree(root, subRoot) true) { return true; } isSubtree(root-left, subRoot-left); isSubtree(root-right, subRoot-right); }错误一递归返回值直接丢掉只写isSubtree(root-left, subRoot-left)虽然调用了递归但返回结果完全没有处理。假设左子树深处真的找到匹配返回 true回到当前层以后既没有 return 也没有保存这个 true 直接被丢掉了。递归不是「调用一下就行」。真正重要的是下层递归计算出来的结果上一层到底如何使用。错误二函数最后没有 return函数声明是bool isSubtree(...)意味着所有执行路径最终都应该返回 true 或者 false。原代码最后两行调用完递归直接结束没有 return。在 C 语言中这会导致未定义行为得到的结果完全不可靠。错误三subRoot 不应该跟着移动原代码写了isSubtree(root-left, subRoot-left)这是逻辑上的根本错误。我们要做的事情是在 root 的不同位置寻找完整的 subRoot。所以每换一个候选位置root 可以变但匹配的目标 subRoot 必须始终保持不变。正确写法isSubtree(root-left, subRoot)而不是subRoot-left。3.5 题后总结 与 || 的选择isSameTreereturn 左边相同 右边相同;—— 两边都必须满足。isSubtreereturn 左边找到 || 右边找到;—— 只需要一个位置能够找到即可。做递归题时不应该机械记忆「二叉树最后都写左右递归」真正应该问自己左右子问题之间到底是「并且」还是「或者」四、LeetCode 144二叉树的前序遍历4.1 题目要求从打印到返回数组LeetCode 144 要求返回二叉树的前序遍历根 → 左 → 右。如果只是本地打印我们可以直接写printf(%d , root-val);。但力扣接口要求int* preorderTraversal(struct TreeNode* root, int* returnSize)也就是说需要动态申请一个数组把前序遍历结果写进去通过returnSize告诉力扣数组中有几个有效元素返回数组首地址。相比本地打印多了一步「结果保存」的工作。4.2 思路先统计结点数再递归填充我们已经实现过二叉树结点总数统计这里直接复用int TreeSize(struct TreeNode* root) { if (root NULL) return 0; return 1 TreeSize(root-left) TreeSize(root-right); }流程先通过TreeSize得到整棵树的结点数赋值给*returnSize根据结点数 malloc 刚好大小的数组定义下标变量递归遍历数组把值依次填入。递归函数BinaryTreePrevOrder(root, arr, pi)的含义是将以 root 为根的二叉树前序遍历结果从数组 arr 的*pi位置开始写入。4.3 完整代码// 统计结点数量 int TreeSize(struct TreeNode* root) { if (root NULL) return 0; return 1 TreeSize(root-left) TreeSize(root-right); } void BinaryTreePrevOrder( struct TreeNode* root, int* arr, int* pi) { if (root NULL) return; arr[(*pi)] root-val; BinaryTreePrevOrder(root-left, arr, pi); BinaryTreePrevOrder(root-right, arr, pi); } int* preorderTraversal( struct TreeNode* root, int* returnSize) { *returnSize TreeSize(root); int* arr (int*)malloc(sizeof(int) * (*returnSize)); int i 0; BinaryTreePrevOrder(root, arr, i); return arr; }4.4 避坑指南为什么不用全局数组一开始容易想到int num[100];然后直接往里写但这种写法不适合力扣提交多组测试会复用全局数据全局变量生命周期覆盖整个程序如果没有每次重置上一组测试数据会残留下来。固定大小不安全固定 100 个结点一旦测试数据超过就会数组越界。更合理的方式永远是先统计数量 → 按实际数量 malloc → 递归填充。指针运算符优先级问题这道题还有一个特别容易写错的表达式*returnSize。如果想表达「returnSize 指向的整数加 1」这么写是错的。因为后缀优先级高于*所以*returnSize 等价于 *(returnSize)也就是说不是数值加一而是让 returnSize 这个指针自己向后移动了。真正想让指向的整数自增应该写(*returnSize);括号不能省。写复杂指针表达式时宁可多加一层括号也不要凭感觉判断。五、TSINGK110二叉树遍历前序建树 中序输出5.1 题目不再给出已经建立好的struct TreeNode*而是直接给出一串前序遍历字符串#表示空结点。要求根据字符串创建二叉树对建立好的二叉树进行中序遍历并输出。示例输入abc##de#g##f###示例输出c b e g d f a5.2 逆向思路从序列还原树之前我们解决的是「树 → 前序遍历 → 序列」而现在反过来了前序序列 → 构建二叉树 → 中序遍历这是第一次真正利用递归创建树结构而不仅仅是读取树。递归函数CreateTree(str, pi)的含义是从str[*pi]开始根据前序序列建立一棵树并返回这棵树的根结点。遇到 # 返回空树如果当前字符是#说明这里是空树下标后移一位返回 NULLif (str[*pi] #) { (*pi); return NULL; }注意即使遇到 #也必须让下标向后走一位否则递归返回以后还是会继续读取同一个 #。非空结点的处理如果不是 #创建当前结点下标后移然后按照前序「根 → 左 → 右」的顺序递归构建左右子树BTNode* root BuyBTNode(str[*pi]); (*pi); root-left CreateTree(str, pi); root-right CreateTree(str, pi); return root;5.3 完整代码#include stdio.h #include stdlib.h typedef char BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; } BTNode; // 创建结点 BTNode* BuyBTNode(BTDataType val) { BTNode* newNode (BTNode*)malloc(sizeof(BTNode)); if (newNode NULL) { perror(malloc); exit(-1); } newNode-data val; newNode-left NULL; newNode-right NULL; return newNode; } // 先序字符串构建二叉树 // pi 为下标指针# 代表空结点 BTNode* CreateTree(char* str, int* pi) { if (str[*pi] #) { (*pi); return NULL; } BTNode* root BuyBTNode(str[*pi]); (*pi); root-left CreateTree(str, pi); root-right CreateTree(str, pi); return root; } // 中序遍历 void InOrder(BTNode* root) { if (root NULL) return; InOrder(root-left); printf(%c , root-data); InOrder(root-right); } int main() { char buf[105]; // 多组输入每行一棵树 while (fgets(buf, sizeof(buf), stdin)) { int i 0; int p 0; // 去掉 fgets 读入的换行符 while (buf[p] ! \0) { if (buf[p] \n) { buf[p] \0; break; } p; } BTNode* root CreateTree(buf, i); InOrder(root); printf(\n); } return 0; }5.4 拓展本地工程化接口这道题做完以后我把这个思路整理成了本地二叉树库的标准接口相比题目版本额外加入了数组长度参数n避免下标越界BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi) { if (*pi n) { return NULL; } if (a[*pi] #) { (*pi); return NULL; } BTNode* newNode BuyBTNode(a[*pi]); (*pi); newNode-left BinaryTreeCreate(a, n, pi); newNode-right BinaryTreeCreate(a, n, pi); return newNode; }这部分完整的本地接口整理放在了数据结构-二叉树五查找、销毁与前序序列建树-CSDN博客 文章中。六、专题总结一条连续的递归学习路线这一篇看起来做了五道完全不同的题但整理之后会发现它们并不是彼此独立的而是一条逐步递进的学习路线。965 单值二叉树理解「当前层条件 左右子树结果」的基本结构第一次体会组合递归结果。100 相同的树从单棵树递归升级为两棵树同步递归同步比较结构与值。572 另一棵树的子树两层递归嵌套外层遍历寻找匹配点内层做完整树比较体会||的使用场景。144 前序遍历从「判断型递归」转向「结果收集型递归」处理动态数组、指针下标、内存管理。TSINGK110 二叉树遍历从「读取树」升级为「创建树」用递归逆向还原树结构。最值得记住的 5 个易错点递归返回值不能直接丢错误isSubtree(...);正确return isSubtree(...);或用变量接收结果再处理。明确哪个参数可以变化572 中 root 是搜索位置可以不断变化但 subRoot 是完整目标树在搜索阶段不能跟着改变。先给递归函数下定义例如isSameTree(p, q)不是「再递归一下左右孩子」而是「判断以 p 和 q 为根的两棵树是否完全相同」。一旦函数含义明确代码通常就容易推出来。左右子树关系是 还是 ||由题目逻辑决定而不是由「二叉树模板」决定。两边都要满足用 一边满足即可用 ||。指针运算符优先级不能忽略*returnSize不等于(*returnSize)宁可多加括号也不要想当然。写在最后进入二叉树专题以后越来越感觉到二叉树题真正训练的并不是「背递归模板」而是如何定义递归问题。当函数定义清楚以后终止条件是什么当前结点做什么左子树返回什么右子树返回什么两个结果怎么组合这些问题通常都会逐渐清晰。本篇从单棵树判断到两棵树比较再到寻找匹配子树、保存遍历结果、利用序列重新建树逐步加深了二叉树递归的复杂度。其中尤其需要反复提醒自己递归调用不是目的递归返回的结果如何被当前层使用才是关键。后续二叉树专题还会继续围绕树的递归关系和经典题型展开把现在已经建立起来的递归思维继续练熟。