二叉树递归练习前序遍历、相同树、对称树与子树判断最近继续做二叉树递归题题目看起来相似但写函数时我总在想递归遇到NULL究竟该返回什么后来发现得先看这个函数想回答什么。遍历是收集结果比较两棵树是回答真假最大深度是返回数字它们的返回值不能套同一个模板。## 144前序遍历不能只printf前序顺序是根、左、右。在本地写遍历时我只要printf就能看输出LeetCode 144 要返回数组因此还要保存每次访问到的值并通过returnSize告诉调用者写入了多少个元素。我一开始不明白为什么递归辅助函数要拿int* index。如果每一层都拿到一个普通int index改变的是这一层自己的副本其他递归调用不一定知道数组已经写到了哪里。传入地址以后大家改的是同一个计数器。例如访问根节点时写入result[*index]随后增加*index左、右子树会继续从新的位置写。另一种写法是让辅助函数返回更新后的下标再把返回值交给下一个调用关键仍然是把新下标传下去。我通过的提交里辅助函数的关键部分是cret[*index]root-val;(*index);preorder(root-left,ret,index);preorder(root-right,ret,index);提交中还先用count(root)算节点数再malloc结果数组最后由returnSize返回实际写入数量。空树直接返回NULL并把*returnSize保持为 0。## 100 和 101比较方向变了“相同的树”要让两棵树对应位置一一相等两个节点都空当前位置相同只有一个空位置不相同都不空时先比值再递归比较左对左、右对右。两边都成立才算相同所以用。creturn isSameTree(p-left, q-left) isSameTree(p-right, q-right);“对称二叉树”看的是镜像。这里不能沿用左对左而是左边的左孩子对右边的右孩子左边的右孩子对右边的左孩子。我把isMirror理解成拿两棵朝向相反的树来比较先检查空节点和值再交叉递归。这样比背函数名更容易记住为什么要交叉。creturn isMirror(p-left, q-right) isMirror(p-right, q-left);## 572判断当前位置相同还得继续找“另一棵树的子树”比前两题多了一层搜索。我最初容易只检查大树当前节点的值就算根节点相同下面结构也可能不同所以要用“相同树”的判断把整棵候选子树比完。如果当前位置不匹配再去大树的左、右子树找。当前位置匹配、左边找到、右边找到满足任何一种就可以因此搜索用||判断两棵候选树的左右部分是否都相同则用。cif (isSameTree(root, subRoot)) { return true;}return isSubtree(root-left, subRoot) || isSubtree(root-right, subRoot);这题对subRoot的约束是非空。我这次通过的代码确实额外写了subRoot NULL时返回true但那是我的边界处理不是题目要求。写递归时边界条件也应该结合题目输入约束来看。## 965空节点和短路求值单值二叉树要检查整棵树的节点值是否一致。我的理解是先处理空节点再看当前节点与存在的孩子是否同值最后递归检查左右子树。读child-val前必须确定child ! NULL用串起条件时如果前面的条件已经为假后面就不会继续求值。这让我对NULL判断和短路求值的关系更有感觉。我的提交先判断左右孩子是否存在、是否和当前节点同值最后返回isUnivalTree(root-left) isUnivalTree(root-right)。这一句会继续检查更深层不能只看当前节点的两个孩子。这几道题的递归时间、空间也可以一起记144 遍历所有节点时间O(n)结果数组占O(n)递归栈占O(h)。100、101、965 的递归判断都可能走遍节点时间是O(n)、递归栈O(h)。572 如果在大树的很多位置都尝试比较小树朴素写法最坏时间O(n×m)递归栈空间O(h₁h₂)。这篇是我对最近学习问题的复盘。写笔记时本地还没有这五题的源码后来从我已通过的 LeetCode C 提交记录中逐题核对、保存了代码并在本地用 GCC 检查。仓库里只放了这些.c文件没有把测试日志或编译产物传上去。源码GitHub · Gitee