二叉树递归核心：先序中序后序、返回值设计与AVL回溯实战

二叉树递归这块我被问过太多次了先序、中序、后序到底怎么才能不背混递归函数到底该返回 int 还是 void为什么一到 AVL 那种需要回溯更新状态的树结构代码就只能照着书抄抄完还是觉得那不是自己的脑子说实话我早年在这些点上也栽过尤其是线索二叉树那个 pre 指针我真调试到半夜。单独学二叉树、单独学递归很多人都不觉得难可这两个东西一旦合体脑子里的调用栈就开始乱。这篇文章不会像教材一样从树的定义开始逐章念我打算把平时最常被人翻车的几个点拆开揉碎讲一遍递归法将一个整数 n 转换成字符串究竟在递归什么二叉树的先序、中序、后序怎么从代码位置确定二叉树求深度时返回值怎么设计从搜索二叉树到 AVL 树的递归插入、删除为什么每一层都要用返回值“接住”中序线索二叉树递归建立时那个 pre 指针到底在干什么最后再看递归二路归并排序为什么它本质上就是二叉树后序思想的另一种投影。这些内容不是只用来应付笔试。嵌入式平台下维护 AVL 树、RTOS 任务栈限制下写递归遍历、面试时让你用链表实现二路归并排序本质上考的都是同一件事你能不能把一个大规模问题拆成两个同构子问题再把子问题的结果正确传回上一层。准备好了的话我们从最容易被看轻的那道热身题开始。1. 用“整数转字符串”热身递归里最容易被忽略的是什么很多学校的 C 语言课本都有这么一道题用递归方法将一个整数 n 转换成字符串。PTA 上还换着花样考了好几次比如“递归法将一个整数 n 转换成字符串”“递归二路归并排序”这些题目出现在练习列表里时不少人的第一反应是这跟数据结构有什么关系其实关系太密切了。先看常见写法void intToStr(int n) { int high n / 10; if (high ! 0) intToStr(high); putchar(n % 10 0); }调用intToStr(12345)输出是12345。但如果你把putchar放到递归调用之前输出就会变成54321。就这么一行代码的位置差异把递归调用和“操作”的先后顺序讲得明明白白。1.1 这个题目的核心把“当前位”和“更高位”分开处理递归处理整数时我们想先输出最高位。可当前函数拿到的 n 是个完整数字位数最高时越往低位越难直接输出于是做法是high n / 10把最高位及以上的剩余部分拆出来先递归处理 high等到最深层递归返回时再输出当前位n % 10。比如intToStr(12345)会一路调用到intToStr(1)最深处先输出字符1然后逐层返回依次输出2、3、4、5。这不是一个“循环变递归”的简单演示它演示了递归里最核心的一个概念访问时机。同一段处理逻辑放在递归调用之前、之后执行顺序截然不同。如果 n 可能是负数还需要额外处理负号例如先输出-再把参数换成-n或对绝对值递归。很多人栽在负数输入上其实就是没想清楚递归函数的输入状态应该是什么。1.2 从线性递归到二叉树递归分支从一条变两条整数转字符串的递归是一条道走到黑的“线性递归”。每一层只调用一次自身调用关系像一条单链表。但二叉树递归不同一个函数体内部会出现两次对自己的调用调用关系从一条线变成一棵树。这棵树长这样f(node) / \ f(node.left) f(node.right) / \ / \ ... ... ... ...这就是理解二叉树递归的关键入口递归过程本身就是一棵树的展开过程。二叉树的数据结构本身就递归定义遇上一个天然递归的执行过程哪怕你给我一棵只有几个结点的树只要递归深度超过三层很多人就开始晕。为什么晕因为在一棵树上的“向下递归”和“向上回溯”交织在一起。你要时刻知道自己现在处于哪一层、刚处理完哪个子树、下一步该往哪走。普通循环有计数器能一眼看到执行位置递归没有显式计数器执行位置隐藏在函数调用栈里。1.3 新手最常见的三种翻车姿势第一个是漏写递归出口。整数转字符串只要 n 除到 0 就层层返回但不少人只写递归调用忘了if (high ! 0)直接导致栈溢出。对应到二叉树递归出口就是root NULL很多人写完递归遍历一跑就 Segment Fault大部分原因是没想明白空指针才是终止标志。第二个是不清楚参数在递归过程中怎么变化。比如有些人想把整数转成字符串存到全局数组里却在每一层递归都重新把数组下标改成 0导致所有结果都写到同一个位置。对应到二叉树就是递归遍历时传了全局长度、全局索引却没意识到每一层递归都可能修改它。第三个更隐蔽是忽略递归返回值。处理整数时如果不把递归结果传回来那递归计算出的东西就是一句空话。二叉树里最常见的例子是“漏掉 return 语句”或者“调用子树递归但不接收返回值”。我后面详细说 BST 删除节点时这个问题有多致命。2. 先序、中序、后序把代码位置摆对口诀自然就记住了二叉树的遍历试题里最经典的问题就是先序遍历、中序遍历、后序遍历到底是怎么确定的很多人靠背口诀“根左右、左根右、左右根”背得很熟一到代码就错。其实不用背。遍历顺序完全取决于代码中“访问当前结点”这条语句写在两次递归调用的什么位置。2.1 三行代码三种顺序用统一模板看void order(BTNode *root) { if (root NULL) return; // 位置 A先访问根 // order(root-left); // 位置 B左子树访问完后访问根 // order(root-right); // 位置 C左右子树都访问完后访问根 }访问代码放在位置 A根最先被处理然后递归左子树再递归右子树这是先序遍历。放在位置 B先完整递归左子树再处理根最后递归右子树这是中序遍历。放在位置 C左、右子树都递归完成回溯到当前结点时才处理根这是后序遍历。为什么是这个顺序因为递归调用不是“同时”发生的。程序执行到order(root-left)时会一头扎进左子树直到左子树全部执行完、函数一层层返回来才会继续往下执行order(root-right)。所以你看到的执行顺序是一条完全确定的时间线。2.2 一棵小树把整个执行过程交代清楚比如这棵树A / \ B C / \ D E递归展开后访问序列分别是遍历方式访问代码位置输出序列先序左递归前访问A B D E C中序左递归后、右递归前访问D B E A C后序两次递归后访问D E B C A很多人卡在“为什么中序是 D B E A C”上。我换个说法中序遍历的规则是对任意一个结点都要先把它的左子树完整走完然后才轮到它自己。A 的左子树是整个 B 树所以必须先输出 B 树的中序序列 DBE然后输出 A。B 的左子树是 D输出 D接着输出 B再走右子树 E。整个过程就像把每个结点夹在它的左子树序列和右子树序列之间。先序为什么是 A 开头因为它的执行习惯是“走到哪就先看谁”。我常用一个生活类比先序是你进一个房间先看自己再进左边的所有房间最后进右边的所有房间中序是你先把左房间全部逛完回到客厅拍个照再逛右房间后序是你把左右房间全逛完离开客厅最后回头拍一张照。2.3 从遍历序列反推二叉树递归切分思想提前登场笔试里爱考的另一类题是“已知先序和中序还原二叉树”。这类题的本质也是递归先序序列第一个结点一定是根拿着根去中序序列里找位置它左边是左子树的中序序列右边是右子树的中序序列再根据左右子树长度把先序序列切分出左右子树的先序序列。两个序列分别递归树就还原了。后序和中序反推同理后序序列最后一个结点是根。只给先序和后序通常不能唯一还原一棵二叉树因为这种组合能确定根却不能可靠区分左子树和右子树的边界只有每个内部结点左右子树都非空时才可能唯一确定。听起来很绕但如果你脑子里始终装着“递归切分区间”这个模型这类题很少出错。遍历题做多了你会发现二叉树递归常见的三种形态已经出现一种递推过程中的“访问”位置决定了最终序列。这和归并排序里 merge 的位置决定算法是不是归并排序是同一条规律。3. 二叉树的深度没那么简单递归返回值里的三个隐蔽陷阱二叉树求深度是递归返回值最有教学意义的入门题。题目短代码不长但能看出一个人到底懂不懂递归在“返回路径”上做了什么。标准解法int treeDepth(BTNode *root) { if (root NULL) return 0; int leftDepth treeDepth(root-left); int rightDepth treeDepth(root-right); return (leftDepth rightDepth ? leftDepth : rightDepth) 1; }递归从根出发一路向下到每个空结点然后从最底层开始逐层返回子树的深度。每次回到父结点比较左右子树的深度取大的那个加上当前结点这一层。整个过程和“后序遍历”的执行路径完全吻合先算左子树再算右子树最后在根上做合并。3.1 陷阱一递归出口返回 0 还是 -1空结点深度按 0 算这是常见约定。叶子结点调用它的左右空子树都返回 0然后取 max 为 0 再加 1得到 1深度正确。如果你把空结点返回 -1那叶子结点就是 -1 和 -1 取大再加 1等于 0最后整体少了一层结果就会是实际深度减一。不同题目对“空树”的深度定义可能不一样。有的题目把叶子结点深度定义为 1空树深度定义为 0有的题目把根结点深度定义为 0空树深度定义为 -1。写代码前先把约定写清楚比什么都重要。3.2 陷阱二求最小深度不能简单把 max 改成 min求二叉树最小深度很多人觉得只要把上面代码里的 max 换成 min 就好。这是高频错误。单独一棵只有左子树的退化树根最小深度显然是 2也就是沿着唯一路径到叶子的层数。但如果简单用 min空左子树深度算 0算出来就变成 1显然是错的。正确写法要区分“空子树”和“非空子树”int minDepth(BTNode *root) { if (root NULL) return 0; if (root-left NULL) return minDepth(root-right) 1; if (root-right NULL) return minDepth(root-left) 1; int left minDepth(root-left); int right minDepth(root-right); return (left right ? left : right) 1; }最大深度可以容忍某个子树为空因为空子树深度 0 不会影响“更大”这一比较最小深度不行0 会让“最小”变成错误方向。你只有在写代码时真的想过“空子树代表一条不存在路径还是深度 0”才可能避开这个坑。3.3 陷阱三重复递归导致时间复杂度失控看一个判断平衡二叉树的初级递归写法bool isBalanced(BTNode *root) { if (root NULL) return true; int left treeDepth(root-left); int right treeDepth(root-right); if (abs(left - right) 1) return false; return isBalanced(root-left) isBalanced(root-right); }逻辑没错但性能极差。每对一个结点调用 treeDepth都会把它的子树重新递归扫一遍上层判断又递归下去总复杂度会退化成 O(n^2)。对于一百万个结点的树这个写法几乎是灾难。常见的改进思路是不单独再查一遍而是在递归返回子树高度的同时夹带“是否平衡”这个信息。返回值设计成普通 int遇到不平衡就返回 -1 作为标记int checkBalance(BTNode *root) { if (root NULL) return 0; int leftTree checkBalance(root-left); if (leftTree -1) return -1; int rightTree checkBalance(root-right); if (rightTree -1) return -1; if (abs(leftTree - rightTree) 1) return -1; return (leftTree rightTree ? leftTree : rightTree) 1; }这就是后面 AVL 树里“用递归返回值维护子树高度”的雏形。递归返回值不一定要表达一个“值”它完全可以表达一种“状态”。能用一次后序遍历完成的事就别反复从上往下递归。4. 从搜索二叉树到AVL递归回溯时每一层都必须“接住”变化搜索二叉树也叫二叉排序树、二叉搜索树定义本身是递归的左子树所有结点小于根右子树所有结点大于根并且左右子树也都是搜索二叉树。正因为这个递归定义它的查找、插入、删除天然适合递归实现。4.1 查找和插入分治路径就是一棵树查找代码很短BSTNode *bstSearch(BSTNode *root, int target) { if (root NULL || root-key target) return root; if (target root-key) return bstSearch(root-left, target); return bstSearch(root-right, target); }每次递归只进入左子树或右子树所以查找路径长度就是树高。普通二叉树查找最坏可能是 O(n)而均衡的搜索二叉树能到 O(logn)思路相当于把数组二分查找搬进了链式结构。插入的递归代码会暴露一个很多人没意识到的关键点BSTNode *bstInsert(BSTNode *root, int key) { if (root NULL) { BSTNode *node createNode(key); return node; } if (key root-key) root-left bstInsert(root-left, key); else if (key root-key) root-right bstInsert(root-right, key); else return root; // 按约定不插入重复值 return root; }我见过太多人写插入漏了最后的return root;或者在主调函数里只写bstInsert(root, key);不接收返回值。在普通工程代码里这样的错误不一定会立刻崩溃但节点会悄悄丢在递归深处。因为递归调用一旦创建了新节点新节点地址必须通过一串返回值向上传递每一层都执行root-left bstInsert(...)或root-right bstInsert(...)最终才能让最顶层的指针指向新结构。递归的向下钻取和向上传递是同一枚硬币的两面。4.2 删除操作三种情况代表递归处理的三种心态删除节点比插入复杂但搞懂了三种情况就通了一半。被删除节点没有孩子直接 free向父节点返回 NULL。被删除节点只有左孩子或只有右孩子free 当前节点向父节点返回唯一的孩子。被删除节点同时有左右孩子最稳妥的做法是用右子树中的最小节点或者左子树中的最大节点替代被删除节点的值然后递归去右子树中找到并删除那个最小节点。代码大概长这样BSTNode *bstDelete(BSTNode *root, int key) { if (root NULL) return NULL; if (key root-key) root-left bstDelete(root-left, key); else if (key root-key) root-right bstDelete(root-right, key); else { if (root-left NULL root-right NULL) { free(root); return NULL; } else if (root-left NULL) { BSTNode *rightChild root-right; free(root); return rightChild; } else if (root-right NULL) { BSTNode *leftChild root-left; free(root); return leftChild; } else { BSTNode *minNode findMin(root-right); root-key minNode-key; root-right