二叉树进阶算法题详解

本文讲解了二叉树部分的6道进阶算法题每道题都配有题目解析 算法思想 代码实现三部分前言二叉树是数据结构中最重要、最常考的主题之一。如果说链表是线性的艺术那么二叉树就是递归的艺术。今天这篇文章带你从六道经典 LeetCode 二叉树进阶题入手覆盖遍历、构造、转换、查找等核心方向帮你搞定二叉树算法题。一、LeetCode 102 / 107 —— 二叉树的层序遍历题目链接102. Binary Tree Level Order Traversal / 107. Binary Tree Level Order Traversal II1.1 题目解析给你一棵二叉树要求按层返回节点值。102 题要求自顶向下107 题要求自底向上。比如这棵树3 / \ 9 20 / \ 15 7输出应该是102 题自顶向下[[3], [9,20], [15,7]] 107 题自底向上[[15,7], [9,20], [3]]1.2 算法思想层序遍历的核心是队列BFS。但关键问题是怎么知道每一层有多少个节点经典做法是引入一个levelSize变量记录当前层的节点数根节点入队时levelSize 1每处理完一层levelSize 队列.size()此时队列里全部是下一层的节点用一个内层循环按levelSize出队刚好处理完一整层一句话总结外层循环控制还有层没处理完内层循环控制当前层有多少节点要处理。对于 107 题的自底向上最简单的方法是复用 102 的代码最后把结果reverse一下。1.3 代码实现classSolution{public:vectorvectorintlevelOrder(TreeNode*root){vectorvectorintvv;// 存最终结果queueTreeNode*q;// BFS 队列intlevelSize0;// 当前层的节点数if(root){q.push(root);levelSize1;// 第一层只有一个根节点}while(!q.empty()){vectorintv;// 存当前层的结果// 按 levelSize 控制刚好处理完当前层的所有节点while(levelSize--){TreeNode*frontq.front();q.pop();v.push_back(front-val);// 把下一层的节点入队if(front-left)q.push(front-left);if(front-right)q.push(front-right);}// 此时队列里全是下一层的节点更新 levelSizelevelSizeq.size();vv.push_back(v);}returnvv;}};107 题自底向上只需要改一行// 在 return 之前加一行reverse(vv.begin(),vv.end());returnvv;二、LeetCode 144 / 94 / 145 —— 二叉树的非递归遍历题目链接144. 前序 / 94. 中序 / 145. 后序2.1 题目解析这是二叉树最基础的三种遍历但要求不用递归用迭代实现。递归写法大家都很熟// 前序递归根-左-右voidpreorder(TreeNode*root){if(!root)return;visit(root);preorder(root-left);preorder(root-right);}// 中序递归左-根-右voidinorder(TreeNode*root){if(!root)return;inorder(root-left);visit(root);inorder(root-right);}// 后序递归左-右-根voidpostorder(TreeNode*root){if(!root)return;postorder(root-left);postorder(root-right);visit(root);}但面试官往往追问不用递归怎么写这就是我们今天要讲的。2.2 算法思想非递归遍历的核心思路是用栈模拟递归的调用过程。递归的本质是系统帮你维护了一个调用栈——当你preorder(root-left)时当前函数的状态包括root和接下来要执行preorder(root-right)这件事被压入栈中。非递归遍历就是手动用stack来模拟这个过程。把三种遍历放在一起对比规律一目了然遍历方式访问时机口诀前序入栈时访问一路向左边走边访问中序出栈时访问一路向左走到头出栈时再访问后序右子树访问完再出栈访问一路向左右子树没访问过就拐过去2.3 前序遍历非递归核心思路访问当前节点 → 入栈保存 → 去左边 → 左边走完了弹栈去右边。classSolution{public:vectorintpreorderTraversal(TreeNode*root){stackTreeNode*s;vectorintv;TreeNode*curroot;while(cur||!s.empty()){// 第1步一路向左边走边访问边入栈while(cur){v.push_back(cur-val);// 访问根s.push(cur);// 入栈保存curcur-left;// 去左边}// 第2步左边走完了弹出栈顶去右边TreeNode*tops.top();s.pop();curtop-right;// 转向右子树}returnv;}};直观理解想象你在走迷宫见到岔路口节点就先记录访问然后一直走左边左边走不通了回到上一个路口走右边。2.4 中序遍历非递归中序和前序的区别只有一个——访问时机从入栈变成出栈。classSolution{public:vectorintinorderTraversal(TreeNode*root){stackTreeNode*st;TreeNode*curroot;vectorintv;while(cur||!st.empty()){// 第1步一路向左走到底只入栈不访问while(cur){st.push(cur);curcur-left;}// 第2步左边走完了从栈顶取出节点访问TreeNode*topst.top();st.pop();v.push_back(top-val);// 出栈时再访问curtop-right;// 转向右子树}returnv;}};为什么中序是出栈时访问因为中序是左-根-右必须等左子树全处理完才能处理根。当节点从栈顶弹出时它的左子树一定已经处理完毕了。2.5 后序遍历非递归后序是最难的一个因为需要判断右子树是否已经被访问过。我们用一个prev指针记录上一个被访问的节点。classSolution{public:vectorintpostorderTraversal(TreeNode*root){TreeNode*curroot;stackTreeNode*s;vectorintv;TreeNode*prevnullptr;// 记录上一个访问过的节点while(cur||!s.empty()){// 第1步一路向左走到底while(cur){s.push(cur);curcur-left;}TreeNode*tops.top();// 取栈顶但先不弹出// 两种情况可以访问栈顶节点// ① 右子树为空不需要处理右边// ② 右子树已经访问过了prev top-rightif(top-rightnullptr||top-rightprev){s.pop();v.push_back(top-val);prevtop;// 更新 prev}else{// 右子树还没访问先转向右边curtop-right;}}returnv;}};关键理解prev就像是一个到此一游的标记。当prev等于top-right时说明右子树已经访问过了可以放心地访问根节点了。三、LeetCode 606 —— 根据二叉树创建字符串题目链接606. Construct String from Binary Tree3.1 题目解析给定一棵二叉树用前序遍历的方式将其转换为括号表示的字符串。规则如下根节点直接输出左子树用()包裹如果左子树为空但右子树不为空也要输出空括号右子树用()包裹如果右子树为空可以省略示例输入: 1 输出: 1(2(4))(3) / \ 2 3 / 4 输入: 1 输出: 1()(3) ← 左子树为空但不省略因为右子树存在 \ 33.2 算法思想这道题是典型的递归字符串构建问题关键在于把情况分类清楚情况左子树处理右子树处理左右都为空省略省略左空右不空输出()输出(右子树)左不空右空输出(左子树)省略左右都不空输出(左子树)输出(右子树)核心逻辑可以简化为只要左子树或右子树有一个不空左子树的括号就必须输出哪怕左子树是空的只有右子树不空时才输出右子树的括号3.3 代码实现classSolution{public:stringtree2str(TreeNode*root){string str;if(rootnullptr){returnstr;}strto_string(root-val);if(root-left||root-right){str(;strtree2str(root-left);str);}else{strtree2str(root-left);}if(root-right){str(;strtree2str(root-right);str);}else{strtree2str(root-right);}returnstr;}};优雅之处这个代码把左空右不空必须输出空括号这条规则自然地嵌入了逻辑中——因为if (root-left || root-right)这个判断会为左空右不空的情况也进入左括号的构建。四、LeetCode 105 / 106 —— 从前序与中序遍历序列构造二叉树题目链接105. 从前序与中序构造 / 106. 从中序与后序构造4.1 题目解析给你两个数组一个是前序遍历的结果一个是中序遍历的结果要求还原出原始的二叉树。preorder [3, 9, 20, 15, 7] inorder [9, 3, 15, 20, 7] 还原结果 3 / \ 9 20 / \ 15 74.2 算法思想这是二叉树中最经典的分治算法。关键洞察是前序遍历的第一个节点一定是整棵树的根节点。在中序遍历中找到这个根节点的位置左边就是左子树右边就是右子树。具体步骤preorder: [3, 9, 20, 15, 7] ↑ 根节点一定是 3 inorder: [9, 3, 15, 20, 7] ↑ 找到 3 的位置下标为 1 左边 [9] → 左子树的中序 右边 [15,20,7] → 右子树的中序然后递归地处理左子树和右子树左子树 preorder: [9, ...] (从 preorder 中取对应长度的部分) inorder: [9] (中序的左边部分) → 根节点 9左右子树都为空 右子树 preorder: [20, 15, 7] (从 preorder 中取对应长度的部分) inorder: [15, 20, 7] (中序的右边部分) → 根节点 20左子树 [15]右子树 [7]4.3 代码实现classSolution{public:// prei: 当前在前序数组中取到第几个元素引用传递递归过程中递增// inbegin, inend: 当前子树在中序数组中的范围TreeNode*_buildTree(vectorintpreorder,vectorintinorder,intprei,intinbegin,intinend){// 区间无效说明是空树if(inbegininend)returnnullptr;// 前序的第一个元素就是当前子树的根TreeNode*rootnewTreeNode(preorder[prei]);// 在中序中找到根的位置introotiinbegin;while(rootiinend){if(inorder[rooti]root-val)break;elserooti;}// 划分左右子树区间递归构建// 中序 [inbegin, rooti-1] rooti [rooti1, inend]root-left_buildTree(preorder,inorder,prei,inbegin,rooti-1);root-right_buildTree(preorder,inorder,prei,rooti1,inend);returnroot;}TreeNode*buildTree(vectorintpreorder,vectorintinorder){inti0;return_buildTree(preorder,inorder,i,0,inorder.size()-1);}};⚡关键细节prei是引用传递每次递归创建根节点时prei这样前序数组就能一直向前推进。因为前序的顺序是根→左→右和递归的顺序天然一致。106 题中序后序的变化后序的最后一个元素是根节点且遍历顺序是左→右→根所以构建顺序要先右子树再左子树因为从后往前取先取到的是右子树的根。五、剑指 Offer 36 / LCR 155 —— 二叉搜索树与双向链表题目链接LCR 155. 将二叉搜索树转化为排序的双向链表5.1 题目解析输入一棵二叉搜索树BST将它转换成一个排序的循环双向链表。要求不能创建任何新节点只能修改指针返回链表中最小的节点即 BST 的最左节点输入: 4 / \ 2 5 / \ 1 3 输出: 1 ⇄ 2 ⇄ 3 ⇄ 4 ⇄ 5 ⇄ 1 (循环)5.2 算法思想关键洞察BST 的中序遍历就是有序的所以我们只需要在做中序遍历的同时把节点串联起来即可。用prev指针记录中序遍历的上一个节点当前节点 cur 和上一个节点 prev 的关系 cur-left prev ← 当前节点的前驱是 prev prev-right cur ← 上一个节点的后继是 cur遍历完成后prev指向最后一个节点最大值再和头节点最小值相连形成循环链表。5.3 代码实现classSolution{public:// cur: 当前节点 prev: 中序遍历的上一个节点引用传递voidInOrderConvert(Node*cur,Node*prev){if(curnullptr)return;// 中序遍历左 → 根 → 右InOrderConvert(cur-left,prev);// 处理当前节点cur-leftprev;// 当前的前驱指向 previf(prev)prev-rightcur;// prev 的后继指向当前prevcur;// 更新 prevInOrderConvert(cur-right,prev);}Node*treeToDoublyList(Node*root){if(rootnullptr)returnnullptr;Node*prevnullptr;InOrderConvert(root,prev);// 找到头节点最左节点Node*headroot;while(head-left)headhead-left;// 形成循环头尾相连head-leftprev;// 头的前驱指向尾prev-righthead;// 尾的后继指向头returnhead;}};精妙之处prev引用传递贯穿整个中序遍历就像是有一根线把节点按顺序串起来。最后把头尾一接闭环完成六、LeetCode 236 —— 二叉树的最近公共祖先题目链接236. Lowest Common Ancestor of a Binary Tree6.1 题目解析给定一棵二叉树和两个节点p、q找出它们最近的公共祖先。输入: root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 1 3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4 输出: 3 节点 5 和节点 1 的最近公共祖先是根节点 36.2 算法思想两种方法方法一判断节点位置法核心思路如果 p 和 q 分别位于当前节点的左右子树中那当前节点就是最近公共祖先如果都在左子树递归去左边找如果都在右子树递归去右边找。对于当前节点 root判断 p 和 q 的位置 - p 在左 q 在右 → root 就是最近公共祖先 - p 在右 q 在左 → root 就是最近公共祖先 - p 在左 q 在左 → 去左子树找 - p 在右 q 在右 → 去右子树找方法二路径法核心思路分别找到从根到 p 和根到 q 的路径路径上的最后一个相同节点就是最近公共祖先。到 p 的路径: 3 → 5 到 q 的路径: 3 → 1 两条路径的栈 pPath: [3, 5] qPath: [3, 1] 对齐长度后同步弹出直到栈顶相同 → 3 就是答案6.3 代码实现方法一位置判断法classSolution{public:// 判断节点 x 是否在 root 的子树中boolIsInTree(TreeNode*root,TreeNode*x){if(rootnullptr)returnfalse;returnrootx||IsInTree(root-left,x)||IsInTree(root-right,x);}TreeNode*lowestCommonAncestor(TreeNode*root,TreeNode*p,TreeNode*q){if(rootnullptr)returnnullptr;// 如果当前节点就是 p 或 q那它就是祖先if(rootp||rootq)returnroot;// 判断 p 和 q 在左右子树中的位置boolpInLeftIsInTree(root-left,p);boolpInRight!pInLeft;boolqInLeftIsInTree(root-left,q);boolqInRight!qInLeft;// 一个在左一个在右 → 当前节点就是最近公共祖先if((pInLeftqInRight)||(qInLeftpInRight))returnroot;// 都在左边 → 递归去左子树找elseif(pInLeftqInLeft)returnlowestCommonAncestor(root-left,p,q);// 都在右边 → 递归去右子树找else// (pInRight qInRight)returnlowestCommonAncestor(root-right,p,q);}};⚠️ 这个方法虽然直观但每次都要遍历子树找节点时间复杂度较高。适合理解思路面试时可以给出更优的方法二。方法二路径法推荐classSolution{public:// 获取从 root 到 x 的路径用栈存储返回值表示是否找到boolGetPath(TreeNode*root,TreeNode*x,stackTreeNode*path){if(rootnullptr)returnfalse;// 不管三七二十一先把当前节点入栈path.push(root);if(rootx)returntrue;// 在左子树中找if(GetPath(root-left,x,path))returntrue;// 在右子树中找if(GetPath(root-right,x,path))returntrue;// 左右都没找到当前节点不在路径上弹出path.pop();returnfalse;}TreeNode*lowestCommonAncestor(TreeNode*root,TreeNode*p,TreeNode*q){stackTreeNode*pPath,qPath;GetPath(root,p,pPath);GetPath(root,q,qPath);// 把两条路径对齐到相同长度while(pPath.size()!qPath.size()){if(pPath.size()qPath.size())pPath.pop();elseqPath.pop();}// 同步弹出直到栈顶相同while(pPath.top()!qPath.top()){pPath.pop();qPath.pop();}returnpPath.top();}};路径法的优势时间复杂度 O(N)每个节点只访问一次。而且思路非常自然——“找到两条路径看它们在哪分叉”。总结六道题目我们梳理一下核心技巧题目核心技巧思路速记层序遍历levelSize控制每层队列 层计数器非递归遍历栈模拟递归一路向左时机不同二叉树→字符串分类讨论递归构建左空右不空括号不能省前序中序构造前序定根中序分左右前序找根中序切分递归构建BST→双向链表中序有序 prev 串联中序遍历边遍历边串联最近公共祖先路径法 / 位置判断法找路径看分叉二叉树的核心是递归。上面所有题目几乎都在用递归。递归的三个要素终止条件一般是root nullptr分解子问题左子树、右子树分别处理合并结果怎么把左右子树的结果组合起来本文是作者学习二叉树算法题的笔记整理如有错误欢迎指正。