1 二叉树路径(10分)
题目内容：
给定一个二叉查找树的节点插入顺序，请重新构建这个二叉查找树，并按从左至右顺序返回所有根节点至叶节点的路径
输入格式:
一行整数，以空格分隔
注：测试用例中不包含重复的数字
输出格式：
按照叶节点由左至右顺序，以“根节点值->节点值->…->叶节点值”输出每条路径，每行输出一条
输入样例：
5 2 6 1 3 7 4
输出样例：
5->2->1
5->2->3->4
5->6->7
注：对应的二叉查找树如下图：
解题思路：
先构造二叉搜索树，接着前序遍历该二叉搜索树，到达叶节点时保存当前路径，最后分行打印所有路径
程序代码：
class TreeNode:
def __init__(self, key, left=None, right=None):
self.key = key
self.val = None
self.leftChild = left
self.rightChild = right
def put(self, key):
if key < self.key:
if self.leftChild:
self.leftChild.put(key)
else:
self.leftChild = TreeNode(key)
else:
if self.rightChild:
self.rightChild.put(key)
else:
self.rightChild = TreeNode(key)
def generateTree():
root = TreeNode(lst[0])
for i in lst[1:]:
root.put(i)
return root
def preorderTree(tree, path):
path += str(tree.key)
if not tree.leftChild and not tree.rightChild:
result.append(path)
else:
path += '->'
if tree.leftChild:
preorderTree(tree.leftChild, path)
if tree.rightChild:
preorderTree(tree.rightChild, path)
lst = [int(num) for num in input().split()]
root = generateTree()
result = []
path = ''
preorderTree(root, path)
for p in result:
print(p)
2 入室抢劫(10分)
题目内容：
一个专业的小偷决定连夜搜刮沿街的房子。每间房都藏有一定的现金；但需要注意的是，这条街上相邻的房间都装有连通的报警系统，一旦相邻的房间同时被偷则会自动报警。请规划方案，使不触发报警器的前提下获得最大的收益。
输入格式:
一行非负整数序列，代表沿街每个房间的收益
输出格式：
一个整数，代表可能的最大收益
输入样例：
2 1 2 3
输出样例：
5
注：同时偷窃下标为 0(收益2)与 3(收益3)的房间，可以获得最大收益5
解题思路：
运用动态规划算法，opt(i)表示偷窃下标前i个房间的最大收益，我们从盗取下标为2的房间开始，盗贼可以选择盗取下标为2的房间，或者选择不盗取，选择盗取下标为2的房间，则opt(2) = opt(0) + value[2]，选择不盗取，则opt(2) = opt(1)，最后opt(2)在两者之间选最大值， 即opt(2) = max(opt(1), opt(0) + value[2])
程序代码：
value = [int(num) for num in input().split()]
N = len(value)
opt = [0 for i in range(N)]
if N == 0:
print(0)
elif N == 1:
print(value[0])
elif N == 2:
print(max(value))
else:
opt[0] = value[0]
opt[1] = max(value[0], value[1])
for i in range(2, N):
opt[i] = max(opt[i - 2] + value[i], opt[i - 1])
print(opt[-1])
原文链接:/Divine0/article/details/106381901
