二进制的叮当喵

Leetcode124. 二叉树中的最大路径和 题目描述 路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。 路径和 是路径中各节点值的总和。 给你一个二叉树的根节点 root ，返回其 最大路径和 。 示例 1： 123输入：root = [1,2,3]输出：6解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6 示例 2： 123输入：root = [-10,9,20,null,null,15,7]输出：42解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42 提示： 树中节点数目范围是 [1,3×104][1,3 \times 10^4][1,3×104] -1000 <= Node.val <= 1000 解题思路 这道题要求得出二叉树内的最大路径和。需要注意的有两点，一是不一定要求从根节点出发到达叶子结点，可以从任意结点出发，到达任意结点；二是结点 ...

Leetcode113. 路径总和 II 题目描述 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 示例 1： 12输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22输出：[[5,4,11,2],[5,8,4,5]] 示例 2： 12输入：root = [1,2,3], targetSum = 5输出：[] 示例 3： 12输入：root = [1,2], targetSum = 0输出：[] 提示： 树中节点总数在范围 [0, 5000] 内 -1000 <= Node.val <= 1000 -1000 <= targetSum <= 1000 解题思路 这道题我们可以直接套用树的DFS遍历模板来求解，但是需要注意实现时的小细节。 在求解的过程中，用全局的二维vector数组path来存储要求解的路径，在DFS函数内部用非引用的一维vector数组tempP ...

Leetcode112. 路径总和 题目描述 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。 叶子节点 是指没有子节点的节点。 示例 1： 12输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22输出：true 示例 2： 12输入：root = [1,2,3], targetSum = 5输出：false 示例 3： 12输入：root = [1,2], targetSum = 0输出：false 提示： 树中节点的数目在范围 [0, 5000] 内 -1000 <= Node.val <= 1000 -1000 <= targetSum <= 1000 解题思路 这道题也是树的遍历的变形应用，可以借鉴Leetcode129. 求根节点到叶节点数字之和中的写法。 同一个全局变量来记录是否存在路径。在空节点的时候直接返回，当遍历到叶子结点的时 ...

Leetcode105. 从前序与中序遍历序列构造二叉树 题目描述 根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如，给出 12前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树： 12345 3 / \9 20 / \ 15 7 解题思路 这道题我们可以运用递归写出非常简洁和通俗易懂的代码，需要注意递归时函数参数的设定。 在求解的过程中，我们主要利用了前序遍历和中序遍历的性质： 对于任意一颗树而言，前序遍历的形式总是： [ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ] 即根节点总是前序遍历中的第一个节点。因此，我们总是可以通过前序遍历找到根节点。 而中序遍历的形式总是： [ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ] 可以看到的是，在中序遍历序列中，在根节点左端的都是左子树的中序遍历结果，在根节点右端的都是右子树的中序遍历结果。只要我们在中序遍历中找到根节点的位置，那么我们就可以确定左子树和右子树的结点数目 ...

Leetcode 103. 二叉树的锯齿形层序遍历 题目描述 给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。 例如： 给定二叉树 [3,9,20,null,null,15,7], 123456789101112 3 / \ 9 20 / \ 15 7返回锯齿形层序遍历如下：[ [3], [20,9], [15,7]] 解题思路 这道题是二叉树层次遍历的变种，可以参照二叉树遍历大总结里面的层次遍历中的方法进行微改动。 由于我们已经加上了level来指示二叉树的层数，那么我们其实只要判断level为奇数的时候，将存储那一层结点值的vector颠倒再加入两层vector就可以了 代码示例 12345678910111213141516171819202122232425262728293031void levelOrder(TreeNode* root,vector<vector<int>>&res,int lev){ if(root== ...

Leetcode101. 对称二叉树 题目描述 给定一个二叉树，检查它是否是镜像对称的。 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。 12345 1 / \ 2 2 / \ / \3 4 4 3 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 12345 1 / \2 2 \ \ 3 3 进阶： 你可以运用递归和迭代两种方法解决这个问题吗？ 解题思路 首先，观察一下什么样的树是对称的。不难发现，如果一个树的左子树与右子树镜像对称，那么这个树是对称的。 更具体地说，如果两个树要镜像对称，那么就要同时满足下面的条件： 他们的两个根节点的值相同 每个树的左子树与另一个树的右子树镜像对称 每个树的右子树与另一个树的左子树镜像对称 据此可以写出递归和迭代版本的代码。 示例代码 递归版本： 123456789101112131415161718bool check1(TreeNode* p,TreeNode* q){ if(p==nullptr&&q==nullptr) return ...

Leetcode98. 验证二叉搜索树 题目描述 给定一个二叉树，判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征： 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 示例 1: 12345输入: 2 / \ 1 3输出: true 示例 2: 123456789输入: 5 / \ 1 4 / \ 3 6输出: false解释: 输入为: [5,1,4,null,null,3,6]。 根节点的值为 5 ，但是其右子节点值为 4 。 解题思路 要想解答这道题，我们先回忆一下二叉搜索树的特性。 二叉搜索树的特性： 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树 二叉搜索树按中序遍历得到的序列是从小到大排列的 根据二叉树的特性我们可以写出判断是否为二叉搜索树的算法。我们可以用前三条特性得出算法一，它的难点在于如何判断一个节点的左子树的所有节点都小于当前节点以及这个节点 ...

Leeetcode93. 复原 IP 地址 题目描述 给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。 例如：“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。 示例 1： 12输入：s = "25525511135"输出：["255.255.11.135","255.255.111.35"] 示例 2： 12输入：s = "0000"输出：["0.0.0.0"] 示例 3： 12输入：s = "1111"输出：["1.1.1.1"] 示例 4： 12输入：s = "010010" ...

Leetcode83. 删除排序链表中的重复元素 题目描述 存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。 返回同样按升序排列的结果链表。 示例 1： 12输入：head = [1,1,2]输出：[1,2] 示例 2： 12输入：head = [1,1,2,3,3]输出：[1,2,3] 提示： 链表中节点数目在范围 [0, 300] 内 -100 <= Node.val <= 100 题目数据保证链表已经按升序排列 解题思路 这道题的思路比较简单。只需要注意在记录指向当前结点的指针的同时，还需要记录指向上一个结点的指针，在当前结点与下一个结点元素相同的时候，将当前节点删除。 这个方法智能运用于有序链表，如果是无序链表中删除重复元素，就需要用哈希表来记录元素出现的次数或者标记是否出现。 示例代码 123456789101112131415161718192021222324252627282930struct ListNode { int val; ListNode *next; ...

Leetcode82. 删除排序链表中的重复元素 II 题目描述 存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。 返回同样按升序排列的结果链表。 示例 1： 12输入：head = [1,2,3,3,4,4,5]输出：[1,2,5] 示例 2： 12输入：head = [1,1,1,2,3]输出：[2,3] 提示： 链表中节点数目在范围 [0, 300] 内 -100 <= Node.val <= 100 题目数据保证链表已经按升序排列 解题思路 这道题与Leetcode83. 删除排序链表中的重复元素很类似，但是与之不同的是这道题并不保留数字重复的结点，只是保留原始链表中不重复元素的结点。 所以我们可以直接套用Leetcode83. 删除排序链表中的重复元素中的方法，但是在删除结点的时候做一点改动：将if判断改为while循环，在循环结束的时候删除最后残留的数字重复的结点。删除代码如下示例： 12345678910if(curPtr->val==curPtr-&g ...