目录一前言二拓展题1二叉树前序迭代遍历2二叉树后序迭代遍历3根据前序和中序遍历序列构建二叉树4判断一棵二叉树是否是平衡二叉树5给定一棵二叉树找到指定两个节点的最近公共祖先一前言在上一篇博客中博主详细讲解了二叉树的相关概念和基本操作为了使我们能够更加深入了解二叉树的结构和使用逻辑故本文精选了一些具有代表性的OJ题进行讲解。在二叉树章节中由于代码逻辑比较抽象文字和静态图片无法直观地表达解题思路和执行流程故博主在本篇博客中会尝试制作动图希望能够提升大家的理解程度。二拓展题1二叉树前序迭代遍历题目144. 二叉树的前序遍历 - 力扣LeetCode144. 二叉树的前序遍历 - 给你二叉树的根节点 root 返回它节点值的 前序 遍历。 示例 1输入root [1,null,2,3]输出[1,2,3]解释[https://assets.leetcode.com/uploads/2024/08/29/screenshot-2024-08-29-202743.png]示例 2输入root [1,2,3,4,5,null,8,null,null,6,7,9]输出[1,2,4,5,6,7,3,8,9]解释[https://assets.leetcode.com/uploads/2024/08/29/tree_2.png]示例 3输入root []输出[]示例 4输入root [1]输出[1] 提示 * 树中节点数目在范围 [0, 100] 内 * -100 Node.val 100 进阶递归算法很简单你可以通过迭代算法完成吗https://leetcode.cn/problems/binary-tree-preorder-traversal/解析迭代遍历二叉树最核心的逻辑为“使用栈保存已经访问过、但右子树还未处理的节点”如此便可以记录回溯路径。在前序迭代遍历二叉树时主要根据遍历变量cur节点的情况做以下操作cur不为空入栈并访问当前节点在该题中访问形式为将节点入返回链表并使 cur cur.left 走向左子树此处完成根 左cur为空出栈栈顶元素top并使 cur top.right 走向右子树cur为空证明当前分支走到尽头而栈顶保存的是上一个已经访问过、但右子树还未处理的节点让 cur top.right 即是继根 左之后走向右完成前序遍历当cur为空且栈为空则证明该二叉树遍历完成对应代码如下while (cur ! null || !stack.isEmpty()) { ... }完整代码逻辑如下图所示注二叉树的前序迭代遍历和中序迭代遍历代码几乎一样区别在于访问节点的时机不同。前序遍历是“入栈即访问”而中序遍历是“出栈再访问”两者都是“一路向左左空回溯转右”。伪代码如下所示// 前序入栈时访问 if (cur ! null) { retList.add(cur.val); // 访问 stack.push(cur); cur cur.left; } else { TreeNode top stack.pop(); cur top.right; } // 中序出栈时再访问 if (cur ! null) { stack.push(cur); cur cur.left; } else { TreeNode top stack.pop(); retList.add(cur.val); // 访问 cur top.right; }完整解题代码/** * 二叉树的前序遍历-迭代实现 * param root 根节点 * return {link List }{link Integer } */ public ListInteger preorderTraversal(TreeNode root) { ListInteger retList new LinkedList(); // 判空 if(root null) { return retList; } // 迭代遍历 StackTreeNode stack new Stack(); TreeNode cur root; while(cur ! null || !stack.isEmpty()) { if(cur ! null) { // -当前节点不为空则入栈向左并在此处打印此时为根左右顺序 stack.push(cur); retList.add(cur.val); cur cur.left; } else { // -当前节点为空则出栈向右 TreeNode top stack.pop(); cur top.right; } } // 返回值 return retList; }2二叉树后序迭代遍历题目145. 二叉树的后序遍历 - 力扣LeetCode145. 二叉树的后序遍历 - 给你一棵二叉树的根节点 root 返回其节点值的 后序遍历 。 示例 1输入root [1,null,2,3]输出[3,2,1]解释[https://assets.leetcode.com/uploads/2024/08/29/screenshot-2024-08-29-202743.png]示例 2输入root [1,2,3,4,5,null,8,null,null,6,7,9]输出[4,6,7,5,2,9,8,3,1]解释[https://assets.leetcode.com/uploads/2024/08/29/tree_2.png]示例 3输入root []输出[]示例 4输入root [1]输出[1] 提示 * 树中节点的数目在范围 [0, 100] 内 * -100 Node.val 100 进阶递归算法很简单你可以通过迭代算法完成吗https://leetcode.cn/problems/binary-tree-postorder-traversal/description/解析后序遍历顺序为左右根由于需要保证在右子树遍历完毕后再打印根节点故出栈条件与前/中序有所不同因此单独进行讲解。在后序迭代遍历二叉树时依旧是根据遍历变量cur节点状态分情况处理但在此基础上还额外添加prev变量记录上一次访问入链表的节点cur不为空入栈当前节点并使 cur cur.left 走向左子树此处完成左 cur为空先使用peek()获取栈顶元素因为此时还不知道右子树是否遍历完毕故不能出栈使用top保存再判断右子树是否访问完毕1右子树访问完毕 出栈栈顶元素并访问在该题中访问形式为将节点入返回链表同时使用prev记录该节点此处完成 右 根注右子树访问完毕的标志有两种1top.right null表示右子树为空此时无需访问2top.right prev表示右子树为上一次访问的节点即右子树已访问完毕上述两种情况满足任意一种即可2右子树未访问 使 cur top.right 走向右子树走向右子树后依旧会按照左右根的顺序进行打印因此可以保证右子树完成访问当cur为空且栈为空则证明该二叉树遍历完成对应代码如下while (cur ! null || !stack.isEmpty()) { ... }完整代码逻辑如下图所示注核心逻辑为先一路向左左空后看栈顶右子树为空或右子树已访问才出栈访问根否则转向右子树完整解题代码/** * 二叉树的后序遍历-迭代实现 * param root 根节点 * return {link List }{link Integer } */ public ListInteger postorderTraversal(TreeNode root) { ListInteger retList new LinkedList(); // 判空 if(root null) { return retList; } // 迭代遍历 StackTreeNode stack new Stack(); TreeNode cur root; TreeNode prev null; while(cur ! null || !stack.isEmpty()) { if(cur ! null) { // -当前节点不为空则入栈向左 stack.push(cur); cur cur.left; } else { // -当前节点为空则判断右子树情况不能直接出栈 TreeNode top stack.peek(); if(top.right null || top.right prev) { // --右子树为空 或者 右子树已遍历 访问 记录 出栈 retList.add(top.val); prev top; stack.pop(); } else { // --否则 继续遍历右子树 cur top.right; } } } // 返回值 return retList; }3根据前序和中序遍历序列构建二叉树题目105. 从前序与中序遍历序列构造二叉树 - 力扣LeetCode105. 从前序与中序遍历序列构造二叉树 - 给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。 示例 1:[https://assets.leetcode.com/uploads/2021/02/19/tree.jpg]输入: preorder [3,9,20,15,7], inorder [9,3,15,20,7]输出: [3,9,20,null,null,15,7]示例 2:输入: preorder [-1], inorder [-1]输出: [-1] 提示: * 1 preorder.length 3000 * inorder.length preorder.length * -3000 preorder[i], inorder[i] 3000 * preorder 和 inorder 均 无重复 元素 * inorder 均出现在 preorder * preorder 保证 为二叉树的前序遍历序列 * inorder 保证 为二叉树的中序遍历序列https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/解析已知本题保证遍历序列正确并且本题树中无重复元素故我们可以得出以下结论1因为前序遍历的顺序是根-左-右所以前序序列的第一个元素就是当前子树的根2拿到这个根值后去中序序列中找到它中序中它左边部分就是左子树右边部分就是右子树3根据1、2逻辑再对左右子树递归重复这一过程4递归时存在以下三种情况当递归至子序列为空时说明该方向没有子树返回null我的实现中为了减少递归次数直接在递归前判断了子序列长度长度小于1时直接赋值为null当子序列只有一个元素时说明该子树是叶子节点创建这个节点后返回当子序列长度大于一时继续递归划分直到变成空或单元素5当所有递归区间都处理完毕整棵树构建完成最终返回整棵树的根节点递归构建过程如下图所示在递推时划分序列在回退时建立联系。注对于此类二叉树递归问题我的经验是不要去深究左右子树的递归细节直接假定递归能够完成任务先写出解决根节点处的解法后续再完善细节。不过有三点需要注意1需要确定递归的返回值一般来说是我们所求的内容以本题为例返回根节点2需要确定递归的参数传递要确保传递下去的参数能够保证下一层也能够完成任务3需要确定递归的终止条件可以套用本层的情况考虑按照此思想我将代码编写思路注释如下完整解题代码public class Solution { private int index 0; /** * 从前序与中序遍历序列构造二叉树 * param preorder 前序遍历序列 * param inorder 中序遍历序列 * return {link TreeNode } */ public TreeNode buildTree(int[] preorder, int[] inorder) { // 递归出口 if(index preorder.length) { return null; } // 创建根节点 int val preorder[index ]; int pivot findIndex(inorder, val); TreeNode root new TreeNode(val); // 递归左右子树 if(pivot 0) { root.left buildTree(preorder, Arrays.copyOfRange(inorder, 0, pivot)); } else { root.left null; } if(inorder.length - pivot 1) { root.right buildTree(preorder, Arrays.copyOfRange(inorder, pivot 1, inorder.length)); } else { root.right null; } // 返回值 return root; } /** * 查找元素并返回下标 * param arr 目标数组 * param t 目标值 * return int 目标值下标 */ private int findIndex(int[] arr, int t) { for(int i 0; i arr.length; i ) { if(arr[i] t) { return i; } } return -1; } }4判断一棵二叉树是否是平衡二叉树题目110. 平衡二叉树 - 力扣LeetCode110. 平衡二叉树 - 给定一个二叉树判断它是否是 平衡二叉树 示例 1[https://assets.leetcode.com/uploads/2020/10/06/balance_1.jpg]输入root [3,9,20,null,null,15,7]输出true示例 2[https://assets.leetcode.com/uploads/2020/10/06/balance_2.jpg]输入root [1,2,2,3,3,null,null,4,4]输出false示例 3输入root []输出true 提示 * 树中的节点数在范围 [0, 5000] 内 * -104 Node.val 104https://leetcode.cn/problems/balanced-binary-tree/description/解析所谓平衡二叉树即是指该树所有节点的左右子树高度相差不超过1。由上述概念可得我们若想判断一棵树是否是平衡二叉树则需要满足“左右子树均为平衡二叉树并且左右子树的高度相差不超过1”。由上述描述我们不难写出解题代码伪代码如下public boolean function(TreeNode node) { // 判空 if(node null) { return true; } // 先判断当前树是否是平衡二叉树 int left getTreeHigh(node.left); int right getTreeHigh(node.right); if(Math.abs(left - right) 1) { return false; } // 再递归判断左右子树是否是平衡二叉树 return function(node.left) function(node.right); } private int getTreeHigh(TreeNode node) { // 判空 if(node null) { return 0; } // 获取左右子树高度取最大值 1返回 int left getTreeHigh(node.left); int right getTreeHigh(node.right); return Math.max(left, right) 1; }以上伪代码思想很直接并且递归很简单同时我们不难发现在function()方法中调用getTreeHigh()方法获取左右子树高度求高度差值以判断当前树是否是平衡二叉树而在getTreeHigh()内部也调用了getTreeHigh()方法获取左右子树高度求左右子树最大高度故我们不禁生出这样的疑问——是否可以在获取树的高度时就判断其是否是平衡二叉树呢答案是可以的由于在getTreeHigh()方法中我们就会获取左右子树高度故当左右子树差值高度超过1时就直接返回-1并且在递归中对-1进行拦截只要返回-1就直接返回那么就可以实现对二叉树的判定。完整解题代码/** * 判断一棵二叉树是否是平衡二叉树 * param root 根节点 * return boolean */ public boolean isBalanced(TreeNode root) { // 直接调用getMaxDepth()方法 return getMaxDepth(root) ! -1; } /** * 获取二叉树的最大深度 * param root 根节点 * return int */ private int getMaxDepth(TreeNode root) { // 判空 if(root null) { return 0; } // 获取左右子树高度并拦截-1 int leftDepth getMaxDepth(root.left); if(leftDepth -1) { return -1; } int rightDepth getMaxDepth(root.right); if(rightDepth -1) { return -1; } if(Math.abs(leftDepth - rightDepth) 1) { return -1; } // 当左右子树均为二叉树且当前左右子树也平衡时返回最大深度 return Math.max(leftDepth, rightDepth) 1; }5给定一棵二叉树找到指定两个节点的最近公共祖先题目236. 二叉树的最近公共祖先 - 力扣LeetCode236. 二叉树的最近公共祖先 - 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科 [https://baike.baidu.com/item/%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88/8918834?fraladdin]中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。” 示例 1[https://assets.leetcode.com/uploads/2018/12/14/binarytree.png]输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 1输出3解释节点 5 和节点 1 的最近公共祖先是节点 3 。示例 2[https://assets.leetcode.com/uploads/2018/12/14/binarytree.png]输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 4输出5解释节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。示例 3输入root [1,2], p 1, q 2输出1 提示 * 树中节点数目在范围 [2, 105] 内。 * -109 Node.val 109 * 所有 Node.val 互不相同 。 * p ! q * p 和 q 均存在于给定的二叉树中。https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/解析由本题提示可知指定的两个节点必定存在于树中。故易得在最差情况下root节点为两个节点的最近公共祖先。我们若是直接上手去做可能感觉有点复杂因为需要判断两个节点的位置情况故本题博主使用一种较为易懂的方式进行解题。我们可以先找到根节点到目标节点路径上所有的节点并使用栈存储起来如此我们便可以得到两个栈如下图示。因为这两条路径都是从root节点开始并且其必定存在公共祖先则从root到最近公共祖先这一段路径一定是相同的从最近公共祖先之后路径开始出现分歧。故将栈元素个数多的一方出栈直至两个栈元素个数相等再同时出栈判断节点是否相同所遇见的第一个相同节点一定是最近公共祖先。注由于路径节点按从根到目标节点的顺序入栈因此栈顶是目标节点栈底是根节点。出栈比较时实际是从目标节点开始沿着路径向上回溯也就是从树的下方往上方比较。先让较长栈出栈至两栈等长使两个节点处于同一深度再同时出栈遇到的第一个相同节点即为最近公共祖先。那么现在我们只需要解决“找到根节点到目标节点路径上所有的节点并使用栈存储起来”这一需求即可。可以使用递归实现该需求逻辑如下DFS找路径每次递归时root存在以下三种情况1root为null 返回null说明这个方向没有我们要找的节点2root为目标节点 将root入栈并返回栈表明已经找到3root为其它节点 将root入栈并递归root的左右子树此时存在两种情况3.1递归左右子树的返回值均为null 出栈栈顶元素因为左右为空说明在左右子树中均未找到目标值故当前根节点不为路径上的节点3.2递归左右子树的返回值不是均为null 返回栈因为左右子树的返回值有一个不为空则说明已经在左/右子树找到目标节点并记录此时直接返回即可/** * 获取根节点到目标节点路径上的所有节点并入栈存储 * param root 根节点 * param t 目标节点 * return {link Stack }{link TreeNode } */ private StackTreeNode getPathStack(StackTreeNode path, TreeNode root, TreeNode t) { // 递归出口 if(root null) { return null; } if(root t) { path.push(root); return path; } // 入栈 path.push(root); // 递归左右树 StackTreeNode leftStack getPathStack(path, root.left, t); StackTreeNode rightStack getPathStack(path, root.right, t); // 根据左右树情况返回 if(leftStack null rightStack null) { path.pop(); return null; } return path; }注在递归完左/右子树后也可以判断其返回值拦截stack这样可以避免在左子树找到后还递归右子树的情况但为了让代码易懂此处就不做优化递归过程如下图所示完整解题代码/** * 二叉树的最近公共祖先 * 由题可知两个节点必定存在则必定存在公共祖先最差情况是root * param root 根节点 * param p 节点1 * param q 节点2 * return {link TreeNode } */ public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // 分别获取两个节点从根节点出发的路径 StackTreeNode stackP getPathStack(new StackTreeNode(), root, p); StackTreeNode stackQ getPathStack(new StackTreeNode(), root, q); // 使两条路径节点个数相等 int len1 stackP.size(); int len2 stackQ.size(); if(len1 len2) { for(int i 0; i len1 - len2; i ) { stackP.pop(); } } else if(len1 len2) { for(int i 0; i len2 - len1; i ) { stackQ.pop(); } } // 同时出栈比较找到相同节点由于是使用栈存储比较顺序为从下往上找因此遇见的第一个相同节点一定是最近的 while(!stackP.isEmpty()) { if(stackP.peek() stackQ.peek()) { return stackP.peek(); } stackP.pop(); stackQ.pop(); } return null; } /** * 获取根节点到目标节点路径上的所有节点并入栈存储 * param root 根节点 * param t 目标节点 * return {link Stack }{link TreeNode } */ private StackTreeNode getPathStack(StackTreeNode path, TreeNode root, TreeNode t) { // 递归出口 if(root null) { return null; } if(root t) { path.push(root); return path; } // 入栈 path.push(root); // 递归左右树 StackTreeNode leftStack getPathStack(path, root.left, t); StackTreeNode rightStack getPathStack(path, root.right, t); // 根据左右树情况返回 if(leftStack null rightStack null) { path.pop(); return null; } return path; }