Hot 100 --- 二叉树与递归

本文概览二叉树方面的算法基本都要使用递归本文系统讲解二叉树的结构和递归的三个核心问题什么时候用递归、递归的开始与结束、怎么编写递归函数并配合五道Hot 100入门题中序遍历、最大深度、翻转二叉树、对称二叉树、二叉树的直径进行说明在刷 LeetCode Hot 100 的过程中你会发现很多题目的标签里都有二叉树。而做二叉树的题目基本上离不开一个工具——递归。很多人做二叉树的题觉得难其实不是二叉树本身难而是没搞懂递归。一旦理解了递归二叉树的很多题目就变得顺理成章了所以本文把二叉树和递归放在一起讲。先讲二叉树的结构理解它的自相似特性再讲递归解决三个核心问题——什么时候用、从哪开始到哪结束、怎么编写最后用五道 Hot 100 入门题中序遍历、最大深度、翻转二叉树、对称二叉树、二叉树的直径来实际演示一、二叉树的结构二叉树是一种每个节点最多有两个子节点的树形结构两个子节点分别称为左孩子left和右孩子right1 / \ 2 3 / \ \ 4 5 6在这棵树中节点 1 是根节点root它是整棵树的入口节点 2 是 1 的左孩子节点 3 是 1 的右孩子节点 4、5、6 是叶子节点它们没有子节点二叉树的关键特征子树也是二叉树以节点 2 为根它的左孩子是 4右孩子是 5这本身就构成了一棵完整的二叉树以节点2为根的子树 以节点3为根的子树 2 3 / \ \ 4 5 6这就是二叉树的递归结构一棵二叉树由根节点、左子树、右子树组成而左子树和右子树本身又是二叉树更形式化地说二叉树的定义本身就是递归的一棵二叉树要么为空null要么由一个根节点 一棵左子树 一棵右子树组成其中左子树和右子树也都是二叉树这个特性非常重要——它是我们使用递归解决二叉树问题的根本原因。既然每个子树都是一棵独立的二叉树那么对整棵树的操作就可以自然地分解为对根节点操作 对左子树做同样操作 对右子树做同样操作以最大深度为例整棵树的最大深度 max(左子树深度, 右子树深度) 1左子树深度 max(左子树的左子树深度, 左子树的右子树深度) 1…一直分解到空子树深度为 01 深度 3 / \ 2 3 深度 2 深度 2 / \ \ 4 5 6 深度 1 深度 1 深度 1每一层的深度都可以由其子树的深度推导出来这就是递归的天然土壤二、递归二叉树方面的算法基本都要使用递归。这是因为二叉树本身的结构就是递归定义的——一棵二叉树由根节点、左子树、右子树组成而左子树和右子树本身又是二叉树。这种自相似的结构天然适合用递归来处理但很多人对递归感到困惑主要有三个问题什么时候用递归、递归从哪开始到哪结束、怎么编写递归函数下面逐一讲解并在讲解过程中配合五道 Hot 100 入门题来说明1. 什么时候使用递归当问题可以被分解为结构相同但规模更小的子问题时就可以用递归所谓结构相同就是子问题和原问题本质上是同一类问题只是规模变小了。二叉树问题天然满足这个条件对整棵树求深度 → 对左子树求深度 对右子树求深度 → 组合得到整棵树的深度对整棵树翻转 → 对左子树翻转 对右子树翻转 → 交换根的左右孩子对整棵树判断对称 → 比较根的左右子树是否镜像对称 → 继续递归比较下一层每个子问题都是原问题在更小规模上的重现。识别这种自相似结构就是判断是否使用递归的关键更具体地说当你发现**“解决当前层的问题需要先解决下一层的同类问题”**时递归就是正确的选择。比如要求整棵树的深度必须先知道左右子树的深度 → 递归要翻转整棵树必须先翻转子树 → 递归要判断整棵树是否对称必须先判断左右子树是否镜像对称 → 递归反过来说如果一个问题不能被分解为同结构的子问题就不适合用递归。比如在二叉树中找到第k小的元素单纯递归不够还需要结合中序遍历的特性2. 递归的开始与结束很多人困惑递归从哪里开始到哪里结束核心认识递归的开始检查和结束条件其实是同一回事以最大深度为例函数的第一行是if(rootnull)return0;这个判断同时承担了两个角色作为入口检查当我们从父节点调用maxDepth(root.left)时如果root.left是 null说明这个方向没有子树需要特殊处理作为终止条件当递归不断深入到达叶子节点的孩子即 null时这个判断让递归停止并开始返回为什么它们是同一回事因为在递归的过程中每个节点都会经历首次进入函数这一步。一个非空节点进入函数后会继续往下递归而一个空节点null进入函数后就是递归的终点用一个具体的例子来说明。假设我们计算maxDepth(节点4)4是叶子节点maxDepth(4) → maxDepth(4.left) maxDepth(null) // 调用左子树 → root null, return 0 // 同一个判断作为终止条件 → maxDepth(4.right) maxDepth(null) // 调用右子树 → root null, return 0 // 同一个判断作为终止条件 → return max(0, 0) 1 1当我们调用maxDepth(null)时从调用者的角度看这是一个新节点的入口检查发现这个节点是 null从递归的角度看这是一个终止条件递归不再继续深入同一条if (root null)判断既是入口检查也是终止条件理解了这一点就不再需要分别思考递归从哪里开始和递归在哪里结束因为它们是同一个判断。你只需要想清楚一件事遇到什么情况应该停止递归这个停止条件自然也就处理了首次进入时节点为空的情况3. 怎么编写递归函数编写递归函数有一个固定模式返回类型 递归函数(参数){// 第一步写结束条件出口if(终止条件){return基础值;}// 第二步写递归调用递的过程左子树结果递归函数(左参数);右子树结果递归函数(右参数);// 第三步组合结果并返回归的过程return组合(左子树结果,右子树结果,当前节点);}第一步必须先写结束条件。这是最重要的原则。如果不先写出口递归就会无限循环下去导致栈溢出。而且正如前面分析的结束条件也同时处理了入口检查的问题第二步是递归调用。根据题意决定需要递归处理哪些子问题。对于二叉树通常是对左子树和右子树分别递归第三步是组合结果。把子问题的结果和当前节点的信息组合起来形成当前层的答案这三步的顺序在不同题目中会有变化先递归再处理后序先拿到子树结果再处理当前节点。如最大深度、翻转二叉树、直径先处理再递归先序先处理当前节点再递归子树穿插处理中序递归左子树 → 处理当前节点 → 递归右子树。如中序遍历处理与递归交织处理和递归交替进行。如对称二叉树但无论哪种变化出口条件永远在最前面三、入门案例讲解下面用五道 Hot 100 入门题来具体展示递归在二叉树问题中的应用。每道题都按照递归三步来分析出口 → 递归调用 → 处理当前节点五道题的 Java 实现代码如下二叉树节点的定义统一为TreeNode包含val、left、right三个字段题目出口条件递归调用处理当前节点中序遍历root null→ returnleft, right添加值到集合在两次递归之间最大深度root null→ return 0left, rightmax(left, right) 1翻转二叉树root null→ return nullleft, right交换左右孩子对称二叉树都null→true / 不匹配→false外侧内侧比较值 递归比较镜像位置直径root null→ return 0left, right更新maxDiameter返回深度不同的是每道题处理当前节点的方式但整体框架完全一样出口判断 → 递归调用 → 处理当前节点1. 二叉树的中序遍历题目要求按照左子树 → 根节点 → 右子树的顺序访问所有节点递归三步分析出口if (root null) return;— 空节点没有值可添加递归调用对左子树和右子树分别中序遍历处理当前节点在递归左子树之后、递归右子树之前把当前节点的值加入集合classSolution{publicListIntegerinorderTraversal(TreeNoderoot){ListIntegerresnewArrayList();inorderTraversal(root,res);returnres;}privatevoidinorderTraversal(TreeNoderoot,ListIntegerres){// 递归出口if(rootnull){return;}// 添加左子树的值到集合if(root.left!null){// 递归调用inorderTraversal(root.left,res);}// 添加当前节点的值res.add(root.val);// 添加右子树的值到集合if(root.right!null){// 递归调用inorderTraversal(root.right,res);}}}这就是中序的含义——根节点在中间处理4 / \ 2 6 / \ 1 3 中序遍历过程 1. 递归左子树(节点2) - 递归左子树(节点1) - 左为空跳过 - 添加 1 - 右为空跳过 - 添加 2 - 递归右子树(节点3) - 左为空跳过 - 添加 3 - 右为空跳过 2. 添加 4 3. 递归右子树(节点6) - 左为空跳过 - 添加 6 - 右为空跳过 结果[1, 2, 3, 4, 6]代码中的执行顺序就是inorderTraversal(left)→res.add(root.val)→inorderTraversal(right)正好对应左→根→右这道题的递归属于穿插处理中序模式先递归左子树再处理当前节点最后递归右子树。根节点的处理被夹在两次递归之间2. 二叉树的最大深度题目要求求二叉树的最大深度递归三步分析出口if (root null) return 0;— 空节点的深度为 0递归调用分别求左子树和右子树的深度组合结果max(左子树深度, 右子树深度) 1— 当前节点的深度 子树最大深度 1自己这一层publicintmaxDepth(TreeNoderoot){if(rootnull)return0;intleftmaxDepth(root.left);intrightmaxDepth(root.right);returnMath.max(left,right)1;}3 / \ 9 20 / \ 15 7 递归过程展示递和归 递向下调用 maxDepth(3) → maxDepth(9), maxDepth(20) maxDepth(9) → maxDepth(null), maxDepth(null) ← 到达叶子准备归 maxDepth(20) → maxDepth(15), maxDepth(7) maxDepth(15) → maxDepth(null), maxDepth(null) ← 到达叶子 maxDepth(7) → maxDepth(null), maxDepth(null) ← 到达叶子 归向上返回 maxDepth(null) 0 ← 终止条件 maxDepth(9) max(0, 0) 1 1 maxDepth(15) max(0, 0) 1 1 maxDepth(7) max(0, 0) 1 1 maxDepth(20) max(1, 1) 1 2 maxDepth(3) max(1, 2) 1 3 最大深度 3这道题完美体现了递归的自相似特性每个节点都在问同一个问题——“我这棵子树有多深”而答案都可以由子树的深度推导出来属于先递归再处理后序模式先拿到左右子树的深度再计算当前节点的深度3. 翻转二叉树题目要求翻转二叉树使每个节点的左右子树交换递归三步分析出口if (root null) return null;— 空节点无需翻转递归调用翻转左子树翻转右子树处理当前节点交换当前节点的左右孩子publicTreeNodeinvertTree(TreeNoderoot){if(rootnull){returnnull;}// 递归调用左子树和右子树invertTree(root.left);invertTree(root.right);// 交换根节点的左子树和右子树swap(root,root.left,root.right);returnroot;}privatevoidswap(TreeNoderoot,TreeNodeleft,TreeNoderight){root.leftright;root.rightleft;}翻转前 翻转后 4 4 / \ / \ 2 7 7 2 / \ / \ / \ / \ 1 3 6 9 9 6 3 1为什么必须先递归翻转子树再交换当前节点的左右孩子因为递归调用是靠root.left和root.right来找到子树的。如果先交换那root.left就指向了原来的右子树root.right指向了原来的左子树递归的方向就反了正确的顺序invertTree(root.left)— 翻转左子树此时 root.left 还是原来的左子树invertTree(root.right)— 翻转右子树此时 root.right 还是原来的右子树swap(root, root.left, root.right)— 交换左右孩子代码中的swap方法只做简单的指针交换root.leftright;// 原来的右孩子变成左孩子root.rightleft;// 原来的左孩子变成右孩子属于先递归再处理后序模式先递归翻转左右子树再交换当前节点的左右孩子。必须后序否则递归方向会反4. 对称二叉树题目要求判断二叉树是否关于中心对称递归三步分析这道题比前面几道复杂一点因为不是单独处理一棵子树而是要同时比较两棵子树是否镜像对称出口两个节点都为 null →return true;两边都空对称一个为 null 另一个不为 null或值不同 →return false;不对称递归调用比较left.left和right.right外侧比较left.right和right.left内侧处理当前节点比较左右节点的值是否相等且两侧递归结果都为 truepublicbooleanisSymmetric(TreeNoderoot){if(rootnull){returntrue;}returnrecur(root.left,root.right);}privatebooleanrecur(TreeNodeleft,TreeNoderight){// 递归出口if(leftnullrightnull){returntrue;}// 判断当前节点是否对称if(leftnull||rightnull||left.val!right.val){returnfalse;}// 递归调用左子树和右子树returnrecur(left.left,right.right)recur(left.right,right.left);}镜像对称的关键在于镜像二字——左子树的左孩子应该和右子树的右孩子对称左子树的右孩子应该和右子树的左孩子对称1 / \ L R ← 要比较L和R是否镜像对称 /\ /\ a b c d 外侧对称a vs dL的左 vs R的右→ recur(L.left, R.right) 内侧对称b vs cL的右 vs R的左→ recur(L.right, R.left)用一个具体的例子展示递归过程1 / \ 2 2 / \ / \ 3 4 4 3 recur(2, 2): - 2 ! null, 2 ! null, 2 2 ✓ - 外侧recur(2.left, 2.right) recur(3, 3) - 3 ! null, 3 ! null, 3 3 ✓ - recur(null, null) → true 外侧的左 vs 右 - recur(null, null) → true 外侧的右 vs 左 - return true true true - 内侧recur(2.right, 2.left) recur(4, 4) - 4 ! null, 4 ! null, 4 4 ✓ - recur(null, null) → true - recur(null, null) → true - return true true true - return true true true 整棵树对称如果某个位置不对称比如左子树有个 3 但右子树对应位置是 null那left null || right null就会命中直接返回 false短路后续的递归调用这道题的出口条件比其他题复杂——需要同时判断两个节点有三种情况都空/一空一非空/都非空。但本质上还是同一个思路遇到什么情况应该停止递归答案是两个都空了就返回 true对称到底了不匹配就返回 false不对称了5. 二叉树的直径题目要求求二叉树中任意两个节点间最长路径的边数递归三步分析出口if (root null) return 0;— 空节点的深度为 0递归调用求左子树深度和右子树深度处理当前节点经过当前节点的最长路径 左子树深度 右子树深度用它更新全局最大直径然后返回当前节点的深度privateintmaxDiameter0;publicintdiameterOfBinaryTree(TreeNoderoot){dfs(root);returnmaxDiameter;}// dfs查找最大深度privateintdfs(TreeNoderoot){if(rootnull){return0;}// 递归调用左子树和右子树intleftDepthdfs(root.left);intrightDepthdfs(root.right);// 更新最大直径maxDiameterMath.max(maxDiameter,leftDepthrightDepth);// 计算当前节点深度returnMath.max(leftDepth,rightDepth)1;}这道题和最大深度非常相似递归函数都在求深度。但多了一个关键点直径不一定经过根节点1 / 2 直径 3路径 5→3→2→4 / \ 3 4 / 5在上面的树中经过根节点 1 的最长路径 左深度 右深度 3 0 3但直径路径经过的是节点 25→3→2→4。在这个例子中经过根节点的路径长度碰巧等于直径但很多时候不是这样1 / 2 直径 4路径 5→3→2→4→6 / \ 3 4 / \ 5 6 经过节点1的路径 4 0 4 经过节点2的路径 2 2 4 ← 直径在这 经过节点3的路径 1 0 1 经过节点4的路径 0 1 1关键理解直径就是某个节点处左深度 右深度的最大值这个节点可能不是根节点。所以我们需要在递归过程中持续更新最大直径而不是只在根节点计算代码中使用maxDiameter全局变量来记录// 每到一个节点都计算经过该节点的直径并尝试更新最大值maxDiameterMath.max(maxDiameter,leftDepthrightDepth);// 然后返回当前节点的深度供上层使用returnMath.max(leftDepth,rightDepth)1;递归过程示例1 / 2 / \ 3 4 / 5 dfs(5): left0, right0 → maxDiameter max(0, 00) 0 → return max(0,0)1 1 dfs(3): left1, right0 → maxDiameter max(0, 10) 1 → return max(1,0)1 2 dfs(4): left0, right0 → maxDiameter max(1, 00) 1 → return max(0,0)1 1 dfs(2): left2, right1 → maxDiameter max(1, 21) 3 ← 在节点2更新了最大直径 → return max(2,1)1 3 dfs(1): left3, right0 → maxDiameter max(3, 30) 3 → return max(3,0)1 4 最终直径 3路径 5→3→2→4可以看到最大直径在节点 2 处被更新为 3这就是直径不一定经过根节点的体现这道题和最大深度的递归结构几乎一样唯一的区别是最大深度只需要最终返回根节点的深度而直径需要在每个节点都检查一次经过这个节点的路径是不是最长的