题目： 路径总和 II：给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。 说明: 叶子节点是指没有子节点的节点。 示例:给定如下二叉树，以及目标和 sum = 22，5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1返回: [ [5,4,11,2], [5,8,4,5]] 思路： 老深度优先了。 程序：# Definition for a binary tree node. # c...
题目： 求根到叶子节点数字之和：给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。 例如，从根到叶子节点路径 1->2->3 代表数字 123。 计算从根到叶子节点生成的所有数字之和。 说明: 叶子节点是指没有子节点的节点。 思路： 深度优先。 程序：# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left...
105. 从前序与中序遍历序列构造二叉树题目来源：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal 题目根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如，给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]返回如下的二叉树：3/ 9 20/ 15 7解题思路思路：递归 在这里，先讲一下前序遍历和中序遍历的概念。前...
题目： 路径总和：给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。 说明: 叶子节点是指没有子节点的节点。 示例: 给定如下二叉树，以及目标和 sum = 22，5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。 思路： 野路子...
题目： 二叉树的层次遍历 II：给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历） 思路： 正常层序遍历结果的逆输出。 程序：# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution:def levelOrderBottom(self, root: TreeNode) -> Li...
题目： 验证二叉搜索树：给定一个二叉树，判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征： 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 思路： 遇到树第一想到了递归，用递归来实现。 程序 ：# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self...
152. 乘积最大子数组题目来源：https://leetcode-cn.com/problems/maximum-product-subarray/ 题目给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。 示例 1: 输入: [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。示例 2: 输入: [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。解题思路思路：动态规划 这道题跟之前【53. 最大子...
31. 下一个排列题目实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。 必须原地修改，只允许使用额外常数空间。 以下是一些例子，输入位于左侧列，其相应输出位于右侧列。 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1解题思路思路：迭代 首先先理解题意，题目中要求【将给定数字序列重新排列成字典序中下一个更...
题目： 加油站：在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。 如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。 说明: 如果题目有解，该答案即为唯一答案。 输入数组均为非空数组，且长度相同。 输入数组中的元素均为非负数。思路： 首先寻找每个...
题目： 二叉树的锯齿形层次遍历：给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。 思路： 使用层序遍历的思路，但是没有用到栈。 程序：# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution:def zigzagLevelOrder(s...
题目： 单词拆分：给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 说明：拆分时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。思路： 动态规划常用思路。 程序：class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:if not s:return Falseif not wordDict:return Falselength = len(s)auxiliary = [False for _ i...
题目： 不同的二叉搜索树 II：给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。 思路： 遍历每一个节点，并且得到每个节点的左右子树，然后获得每个子树的样子就可以得出来了。 自己想了半天没法实现，参考了一下网上大神的程序，写的很好，很好理解。 程序：# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # s...
题目： 打家劫舍 II：你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。 思路： 因为首尾两家相连，因此在一些执行的过程...
题目： 搜索二维矩阵 II：编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：? 每行的元素从左到右升序排列。 每列的元素从上到下升序排列。 思路： 二分查找常规思路。 程序： class?Solution: ????def?searchMatrix(self,?matrix,?target): ????????""" ????????:type?matrix:?List[List[int]] ????????:type?target:?int ????????:rtype:?bool ????????""" ????????if?not?matrix: ?????...
题目： 解码方法：一条包含字母 A-Z 的消息通过以下方式进行了编码：? 'A' -> 1 'B' -> 2 ... 'Z' -> 26 给定一个只包含数字的非空字符串，请计算解码方法的总数。?? 思路： 一开始理解错题目了，使用字典去对应，发现题目要求不是这样的。 之后使用动态规划来做，需要考虑的情况比较多，踩了很多坑。 程序： class?Solution: ????def?numDecodings(self,?s:?str)?->?int: ????????if?not?s: ????????????return?0 ????????if?s[0]...