1. 路径总和 II
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：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：
输入：root = [1,2,3], targetSum = 5
输出：[]
示例 3：
输入：root = [1,2], targetSum = 0
输出：[]
提示：
- 树中节点总数在范围
[0, 5000]内 -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
出处：
https://edu.csdn.net/practice/25658336
代码：
from typing import List class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]: pathvalue = 0 path = [] result = [] def preorder(node, pathvalue, sum, path, result): if node == None: return pathvalue += node.val path.append(node.val) if pathvalue == sum and node.left == None and node.right == None: result.append(list(path)) # 注意加list preorder(node.left, pathvalue, sum, path, result) preorder(node.right, pathvalue, sum, path, result) pathvalue -= node.val path.pop() preorder(root, pathvalue, sum, path, result) return result def listToTree(lst: List[int]) -> TreeNode: if not lst: return None root = TreeNode(lst[0]) queue = [root] i = 1 while i < len(lst): node = queue.pop(0) if lst[i] is not None: node.left = TreeNode(lst[i]) queue.append(node.left) i += 1 if i < len(lst) and lst[i] is not None: node.right = TreeNode(lst[i]) queue.append(node.right) i += 1 return root #%% s = Solution() null = None nums = [5,4,8,11,null,13,4,7,2,null,null,5,1] root = listToTree(nums) targetSum = 22 print(s.pathSum(root, targetSum))
输出：
[[5, 4, 11, 2], [5, 8, 4, 5]]
2. 两数相除
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
示例 1:
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2
提示：
- 被除数和除数均为 32 位有符号整数。
- 除数不为 0。
- 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。
出处：
https://edu.csdn.net/practice/25658337
代码：
import math class Solution(object): def divide(self, dividend, divisor): if divisor == 0: return math.inf #MAX_INT if dividend == 0: return 0 isPositive = (dividend < 0) == (divisor < 0) m = abs(dividend) n = abs(divisor) res = math.log(m) - math.log(n) res = int(math.exp(res)) if isPositive: return min(res, 2147483647) return max(0 - res, -2147483648) if __name__ == '__main__': s = Solution() print(s.divide(10, 3)) print(s.divide(7, -3)) print(s.divide(1, 0))
输出：
3
-2
inf
3. 不同的二叉搜索树 II
给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
示例 1：
输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
示例 2：
输入：n = 1
输出：[[1]]
提示：
1 <= n <= 8
出处：
https://edu.csdn.net/practice/25658338
代码：
class TreeNode(object): def __init__(self, x): self.val = x self.left = None self.right = None def to_list(self, count): queue = [] queue.append(self) result = [] while len(queue) > 0: if count == 0: break node = queue.pop(0) if node is None: result.append('null') else: count -= 1 result.append(node.val) queue.append(node.left) queue.append(node.right) return result class Solution(object): def generateTrees(self, n): """ :type n: int :rtype: List[TreeNode] """ if n == 0: return [] return self.get_trees(1, n) def get_trees_impl(self, start, end): trees = [] if start > end: trees.append(None) return trees for i in range(start, end + 1): lefts = self.get_trees_impl(start, i - 1) rights = self.get_trees_impl(i + 1, end) for j in range(len(lefts)): for k in range(len(rights)): root = TreeNode(i) root.left = lefts[j] root.right = rights[k] trees.append(root) return trees def get_trees(self, start, end): trees = self.get_trees_impl(start, end) results = [] for tree in trees: if tree is None: results.append([]) else: results.append(tree.to_list(end)) return results # %% s = Solution() print(s.generateTrees(n=3))
输出：
[[1, 'null', 2, 'null', 3], [1, 'null', 3, 2], [2, 1, 3], [3, 1, 'null', 'null', 2], [3, 2, 'null', 1]]
🌟 每日一练刷题专栏 🌟
✨持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
