C++

106. Construct Binary Tree from Inorder and Postorder TraversalGiven two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree. Example 1: 12Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]Output: [3,9,20,null,null,15,7] Example 2: 12Input: inorder = [-1], postorder = [-1]Output: [-1] 题目大意给定一棵二叉树的中序遍历数组 inorder 和后序遍历数组 postorder，请构造并返回这棵二叉树。 例如： ...

105. Construct Binary Tree from Preorder and Inorder Traversal题目Given preorder and inorder traversal of a tree, construct the binary tree. **Note:**You may assume that duplicates do not exist in the tree. For example, given preorder = [3,9,20,15,7] inorder = [9,3,15,20,7] Return the following binary tree: 3 / \ 9 20 / \ 15 7 题目大意根据一棵树的前序遍历与中序遍历构造二叉树。 注意:你可以假设树中没有重复的元素。 解题思路 inorder_map：用于快速查找中序遍历中元素对应的索引，时间复杂度 O (1) pre：保存前序遍历数组的副本，避免在递归中反复传递参数 确定根节点：前序遍历的第一个元素为当前树的根节点 划分左右...

104. Maximum Depth of Binary TreeGiven the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Example 1: 12Input: root = [3,9,20,null,null,15,7]Output: 3 Example 2: 12Input: root = [1,null,2]Output: 2 题目大意给定一棵二叉树的根节点 root，返回该二叉树的最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数量。 例如： 输入二叉树 [3,9,20,null,null,15,7]，其最大深度为 3（路径：3 → 20 → 15 或 3 → 20 → 7，均包含 3 个节点）。 解题思路计算二叉树的最...

103. Binary Tree Zigzag Level Order Traversal Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between). Example 1: 12Input: root = [3,9,20,null,null,15,7]Output: [[3],[20,9],[15,7]] Example 2: 12Input: root = [1]Output: [[1]] Example 3: 12Input: root = []Output: [] 题目大意给定一棵二叉树的根节点，返回其节点值的锯齿形层序遍历。即：第一层从左到右，第二层从右到左，第三层再从左到右，以此类推，交替进行。 例如： 输入 root = [3,9,20,null...

102. Binary Tree Level Order TraversalGiven the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level). Example 1: 12Input: root = [3,9,20,null,null,15,7]Output: [[3],[9,20],[15,7]] Example 2: 12Input: root = [1]Output: [[1]] Example 3: 12Input: root = []Output: [] 题目大意给定一棵二叉树的根节点 root，返回其节点值的层序遍历结果（即从左到右、逐层遍历）。结果需以二维数组形式呈现，每一层的节点值构成一个子数组（例如，第一层 [根节点]，第二层 [左子节点, 右子节点]，以此类推）。 解题思路层序遍历的核心是按照树的层次依次访问节点，从根节点开始，先访问第一层（根节点）...

101. Symmetric TreeGiven the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center). Example 1: 12Input: root = [1,2,2,3,4,4,3]Output: true Example 2: 12Input: root = [1,2,2,null,3,null,3]Output: false 题目大意给定一棵二叉树的根节点 root，判断该二叉树是否是对称的（即围绕中心轴镜像对称）。 例如： 输入二叉树 [1,2,2,3,4,4,3]，其左子树与右子树成镜像，故返回 true； 输入二叉树 [1,2,2,null,3,null,3]，左子树与右子树不镜像，故返回 false。 解题思路判断二叉树是否对称的核心是比较左子树与右子树是否成镜像，即： 左子树的左节点需与右子树的右节点值相等； 左子树的右节点需与右子树的左节点值相等。 1. 递归法设计一个辅助函数，比较两个子树...

100. Same TreeGiven the roots of two binary trees p and q, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value. Example 1: 12Input: p = [1,2,3], q = [1,2,3]Output: true Example 2: 12Input: p = [1,2], q = [1,null,2]Output: false Example 3: 12Input: p = [1,2,1], q = [1,1,2]Output: false 题目大意给定两棵二叉树的根节点 p 和 q，判断这两棵树是否相同。两棵树相同的定义是：结构完全相同，且对应节点的值也相同。 例如： 输入两棵结构和节点值均相同的树 [1,2,3]...

99. Recover Binary Search TreeYou are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure. Example 1: 123Input: root = [1,3,null,null,2]Output: [3,1,null,null,2]Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid. Example 2: 123Input: root = [3,1,4,null,null,2]Output: [2,1,4,null,null,3]Explanation: 2 cannot be in the right subt...

98. Validate Binary Search TreeGiven the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows: The left subtree of a node contains only nodes with keys strictly less than the node's key. The right subtree of a node contains only nodes with keys strictly greater than the node's key. Both the left and right subtrees must also be binary search trees. Example 1: 12Input: root = [2,1,3]Output: true Example 2: 123Input: root = [...

96. Unique Binary Search TreesGiven an integer n, return *the number of structurally unique **BST'*s (binary search trees) which has exactly n nodes of unique values from 1 to n. Example 1: 12Input: n = 3Output: 5 Example 2: 12Input: n = 1Output: 1 题目大意给定一个整数 n，计算由 1 到 n 为节点所组成的结构独特的二叉搜索树（BST）的数量。 例如： 输入 n = 3，存在 5 种结构独特的 BST，返回 5； 输入 n = 1，只有 1 种 BST，返回 1。 解题思路计算独特 BST 的数量可以通过动态规划（DP） 实现，核心思路基于以下观察： 若选择 i 作为根节点，则左子树由 1~i-1 构成，右子树由 i+1~n 构成； 左子树的独特结构数量为 dp[i-1]，右子树的独特结构数量为 dp[n-i]（...

95. Unique Binary Search Trees IIGiven an integer n, return *all the structurally unique **BST'*s (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order. Example 1: 12Input: n = 3Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]] Example 2: 12Input: n = 1Output: [[1]] 题目大意给定一个整数 n，生成所有由 1 到 n 为节点所组成的结构独特的二叉搜索树（BST）。返回这些二叉搜索树的根节点列表。 二叉搜索树的特性是：对于任意节点，其左子树中的所有节点值都小于该节点值，右子树中的所有节点值都大于该节点值。 例如： 输入 n = 3，存在...

94. Binary Tree Inorder TraversalGiven the root of a binary tree, return the inorder traversal of its nodes' values. Example 1: Input: root = [1,null,2,3] Output: [1,3,2] Explanation: Example 2: Input: root = [1,2,3,4,5,null,8,null,null,6,7,9] Output: [4,2,6,5,7,1,3,9,8] Explanation: Example 3: Input: root = [] Output: [] Example 4: Input: root = [1] Output: [1] 题目大意 给定一棵二叉树的根节点 root，返回其节点值的中序遍历结果。中序遍历的顺序是「左子树 → 根节点 → 右子树」，遵循 “左 - 根 - 右” 的递归逻辑，且需按此顺序收集所有节点值。 解题思路二叉...

93. Restore IP AddressesA valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros. For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses. Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots ...

90. Subsets IIGiven an integer array nums that may contain duplicates, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order. Example 1: 12Input: nums = [1,2,2]Output: [[],[1],[1,2],[1,2,2],[2],[2,2]] Example 2: 12Input: nums = [0]Output: [[],[0]] 题目大意给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（即幂集）。幂集需包含所有可能的子集（包括空集和数组本身），且不能有重复子集，结果顺序可任意。 例如： 输入 nums = [1,2,2]，输出 [[],[1],[1,2],[1,2,2],[2],[2,2]]（共 6 个子集，无重复）； 输入 nums =...

86. Partition ListGiven the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions. Example 1: 12Input: head = [1,4,3,2,5,2], x = 3Output: [1,2,2,4,3,5] Example 2: 12Input: head = [2,1], x = 2Output: [1,2] 题目大意给定链表的头节点 head 和一个值 x，要求将链表分隔成两部分：所有值小于 x 的节点排在所有值大于或等于 x 的节点之前。同时需要保留两部分中节点的原始相对顺序。 解题思路可以通过构建两个临时链表来解决： 创建两个虚拟头节点，分别用于...

84. 柱状图中最大的矩形给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。 示例 1: 123输入：heights = [2,1,5,6,2,3]输出：10解释：最大的矩形为图中红色区域，面积为 10 示例 2： 12输入： heights = [2,4]输出： 4 解题思路该解法是对单调栈思路的优化实现，通过在数组末尾添加哨兵元素和栈初始化技巧，将左右边界的计算合并到一次遍历中，代码更简洁且效率更高。 核心优化思路 哨兵元素（Sentinel）： 在原数组末尾添加 -1（高度为负数的哨兵），确保遍历结束时栈中所有元素都会被弹出计算（相当于 “大火收汁”）； 栈初始时推入 -1（索引哨兵），解决栈空时的边界判断问题，同时自然对应 “左侧无更矮柱子” 的情况（left[i] = -1）。 一次遍历计算左右边界： 遍历每个元素作为右侧边界（right），当当前高度小于栈顶高度时，栈顶元素的左右边界均已确定： 右边界：当前索引 right（第一个比栈顶元素矮的位置）； 左边界：弹出栈...

82. Remove Duplicates from Sorted List IIGiven the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well. Example 1: 12Input: head = [1,2,3,3,4,4,5]Output: [1,2,5] Example 2: 12Input: head = [1,1,1,2,3]Output: [2,3] 题目大意给定一个已排序的链表，要求删除所有存在重复的节点（即重复的节点一个都不保留），仅保留原链表中只出现过一次的节点，最终返回排序后的新链表头节点。 核心解题思路由于链表已排序，重复节点必然相邻，因此可通过「遍历链表 + 跳过重复节点」的思路解决，关键是： 虚拟头节点：避免删除头节点时的特殊处理（如示例 2 中头节点 ...

78. SubsetsGiven an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order. Example 1: 12Input: nums = [1,2,3]Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] Example 2: 12Input: nums = [0]Output: [[],[0]] 题目大意给定一个无重复元素的整数数组 nums，返回该数组所有可能的子集（即幂集）。幂集需包含所有可能的子集（包括空集和数组本身），且不能有重复子集，结果顺序可任意。 例如： 输入 nums = [1,2,3]，输出 [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]（共 2³=8 个子集）； ...

77. CombinationsGiven two integers n and k, return all possible combinations of k numbers chosen from the range [1, n]. You may return the answer in any order. Example 1: 1234Input: n = 4, k = 2Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]Explanation: There are 4 choose 2 = 6 total combinations.Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination. Example 2: 123Input: n = 1, k = 1Output: [[1]]Explanation: There is 1 choose 1 = 1 total combinat...

76. Minimum Window Substring题目Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). Example: 12Input: S = "ADOBECODEBANC", T = "ABC"Output: "BANC" Note: If there is no such window in S that covers all characters in T, return the empty string "". If there is such window, you are guaranteed that there will always be only one unique minimum window in S. 题目大意给定一个源字符串 s，再给一个字符串 T，要...

74. 搜索二维矩阵给你一个满足下述两条属性的 m x n 整数矩阵： 每行中的整数从左到右按非严格递增顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。 示例 1： 12输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3输出：true 示例 2： 12输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13输出：false 解法1：二分查找由于矩阵具有特殊的有序性，可以将其视为一个有序的一维数组来处理： 整个矩阵可以看作是按行拼接而成的有序数组 使用二分查找高效定位目标值 通过计算将一维索引转换为二维矩阵的行和列 1234567891011121314151617181920212223242526272829303132class Solution {public: bool searchM...

73. Set Matrix Zeroes题目Given an *m* x *n* matrix. If an element is 0, set its entire row and column to 0. Do it in-place. Follow up: A straight forward solution using O(mn) space is probably a bad idea. A simple improvement uses O(m + n) space, but still not the best solution. Could you devise a constant space solution? Example 1: 12Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]Output: [[1,0,1],[0,0,0],[1,0,1]] Example 2: 12Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]Output: [[0,0,0,0],[0,4,...

72. Edit DistanceGiven two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have the following three operations permitted on a word: Insert a character Delete a character Replace a character Example 1: 123456Input: word1 = "horse", word2 = "ros"Output: 3Explanation: horse -> rorse (replace 'h' with 'r')rorse -> rose (remove 'r')rose -> ros (remove 'e') Example 2: 12...

71. Simplify PathYou are given an absolute path for a Unix-style file system, which always begins with a slash '/'. Your task is to transform this absolute path into its simplified canonical path. The rules of a Unix-style file system are as follows: A single period '.' represents the current directory. A double period '..' represents the previous/parent directory. Multiple consecutive slashes such as '//' and '///' are treated as a single slash &...

70. Climbing Stairs题目You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Note: Given n will be a positive integer. Example 1: Input: 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps Example 2: Input: 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step ...