算法题--包含1~n的所有二叉搜索树
2020-04-27 本文已影响0人
岁月如歌2020
image.png
0. 链接
1. 题目
Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.
Example:
Input: 3
Output:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
2. 思路1：递归
- 以任何一点作为根节点, 然后分别处理左右子树
- 处理左右子树的问题，仍然与处理根节点的问题的逻辑相同
- 递归函数参数为起止数字, 返回为子树的根节点列表
3. 代码
# coding:utf8
from typing import List
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def generateTrees(self, n: int) -> List[TreeNode]:
def generate(start, end):
res = list()
if start > end:
res.append(None)
for i in range(start, end + 1):
leftlist = generate(start, i - 1)
rightlist = generate(i + 1, end)
for leftnode in leftlist:
for rightnode in rightlist:
root = TreeNode(i)
root.left = leftnode
root.right = rightnode
res.append(root)
return res
if n == 0:
return list()
else:
return generate(1, n)
def print_binary_tree(root):
def collect_nodes(parent, node, results):
if node is None:
return
parent_val = parent.val if parent is not None else 0
results.append((parent_val, node.val))
if node.left is None:
results.append((node.val, None))
else:
collect_nodes(node, node.left, results)
if node.right is None:
results.append((node.val, None))
else:
collect_nodes(node, node.right, results)
results = list()
collect_nodes(None, root, results)
print(results)
solution = Solution()
print('n = 2')
trees = solution.generateTrees(2)
for tree in trees:
print_binary_tree(tree)
print('\nn = 3')
trees = solution.generateTrees(3)
for tree in trees:
print_binary_tree(tree)
输出结果
n = 2
[(0, 1), (1, None), (1, 2), (2, None), (2, None)]
[(0, 2), (2, 1), (1, None), (1, None), (2, None)]
n = 3
[(0, 1), (1, None), (1, 2), (2, None), (2, 3), (3, None), (3, None)]
[(0, 1), (1, None), (1, 3), (3, 2), (2, None), (2, None), (3, None)]
[(0, 2), (2, 1), (1, None), (1, None), (2, 3), (3, None), (3, None)]
[(0, 3), (3, 1), (1, None), (1, 2), (2, None), (2, None), (3, None)]
[(0, 3), (3, 2), (2, 1), (1, None), (1, None), (2, None), (3, None)]
4. 结果
image.png
5. 思路2: 动态规划
- 观察到一个事实, [1 2]的可列树结构, 与[99,100]的可列树结构之间, 具有结构相同的特性，只是数值上相差一个98
- 利用这个事实, 可以大量复用长度相同的连续数字构成的子树计算结果
6. 代码
class Solution2:
def generateTrees(self, n: int) -> List[TreeNode]:
dp = [None] * (n + 1)
dp[0] = list()
if n == 0:
return dp[0]
dp[0].append(None)
# 长度为1到n
for len in range(1, n + 1):
dp[len] = list()
# 将不同的数字作为根节点, 且只需考虑1到len
for root in range(1, len + 1):
left = root - 1
right = len - root
for lefttree in dp[left]:
for righttree in dp[right]:
tree_root = TreeNode(root)
tree_root.left = lefttree
tree_root.right = self.copy_tree(righttree, root)
dp[len].append(tree_root)
return dp[n]
def copy_tree(self, root, offset):
if root is None:
return None
node = TreeNode(root.val + offset)
node.left = self.copy_tree(root.left, offset)
node.right = self.copy_tree(root.right, offset)
return node
def print_binary_tree(root):
def collect_nodes(parent, node, results):
if node is None:
return
parent_val = parent.val if parent is not None else 0
results.append((parent_val, node.val))
if node.left is None:
results.append((node.val, None))
else:
collect_nodes(node, node.left, results)
if node.right is None:
results.append((node.val, None))
else:
collect_nodes(node, node.right, results)
results = list()
collect_nodes(None, root, results)
print(results)
solution = Solution2()
print('n = 2')
trees = solution.generateTrees(2)
for tree in trees:
print_binary_tree(tree)
print('\nn = 3')
trees = solution.generateTrees(3)
for tree in trees:
print_binary_tree(tree)
输出结果
n = 2
[(0, 1), (1, None), (1, 2), (2, None), (2, None)]
[(0, 2), (2, 1), (1, None), (1, None), (2, None)]
n = 3
[(0, 1), (1, None), (1, 2), (2, None), (2, 3), (3, None), (3, None)]
[(0, 1), (1, None), (1, 3), (3, 2), (2, None), (2, None), (3, None)]
[(0, 2), (2, 1), (1, None), (1, None), (2, 3), (3, None), (3, None)]
[(0, 3), (3, 1), (1, None), (1, 2), (2, None), (2, None), (3, None)]
[(0, 3), (3, 2), (2, 1), (1, None), (1, None), (2, None), (3, None)]
结果
image.png
