95. 不同的二叉搜索树 II
95. 不同的二叉搜索树 II
https://leetcode-cn.com/problems/unique-binary-search-trees-ii/
给定一个整数 n，生成所有由 1 ... n 为节点所组成的 二叉搜索树 。
示例：
输入：3
输出：
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
解释： 以上的输出对应以下 5 种不同结构的二叉搜索树：
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
提示：
- 0 <= n <= 8
通过次数36,941 | 提交次数58,220
First Try
2020-07-17
折腾了大半天的题目，本来是一道非常简单的题目才对。
这是参考题解搞出来的，从下到上的递归方法，先求接触所有左子树和右子树，然后一路往上走。
而我尝试的方法是从上到下的递归方法，获得根节点，然后一路递归下去。问题是一直无法判断何时递归结束，思考了几个小时，包括在vscode中调试，知道了问题所在，但不知道如何解决。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
def gen_trees(start, end):
if start > end:
return [None]
rv = []
for i in range(start, end + 1):
left_trees = gen_trees(start, i - 1)
right_tress = gen_trees(i + 1, end)
for lt in left_trees:
for rt in right_tress:
root = TreeNode(i)
root.left = lt
root.right = rt
rv.append(root)
return rv
if n == 0:
return []
return gen_trees(1, n)
- 执行用时：40 ms, 在所有 Python 提交中击败了84.84%的用户
- 内存消耗：15.8 MB, 在所有 Python 提交中击败了33.33%的用户
Failed Try
2020-07-17
太惨了，浪费了从早上到下午四点的大半天时间。
尝试的方法是从上到下的递归方法，获得根节点，然后一路递归下去。问题是一直无法判断何时递归结束，思考了几个小时，包括在vscode中调试，知道了问题所在，但不知道如何解决。
本来应该是使用backtrack简单搞定的，但问题在当两个递归交叉的时候，很难判断什么时候递归结束，何时把添加进去的used中的left和right撤销。因为就算在某个递归节点出现了left和right都为None的情况，也不代表次数可以把used中的left和right撤销，因为在另一侧的大分支上，可能还没有走完。 在这种笛卡尔交互递归的过程中，left和right可以在任意的子路径上出现同时为None的情况，但这棵树还未递归到底。
使用vscode调试，可以发现最后其实root整棵树已经构建完毕，但是无法知道什么时候已经构建完毕，导致无法正确添加数值。
在n=4的时候，可以发现3开头的树都不存在。 这就是bug.
# 太惨了
class Solution(object):
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
def clone(node):
if not node:
return node
nnode = TreeNode(node.val)
nnode.left = clone(node.left)
nnode.right = clone(node.right)
return nnode
def backtrack(root, node, arr, used, n, rv):
if len(used) == n: # 终于把所有点都用光
rv.append(clone(root))
left = [a for a in arr if a < node.val] or [None]
right = [a for a in arr if a > node.val] or [None]
for lft in left:
if lft:
node.left = TreeNode(lft)
used.add(lft)
backtrack(root, node.left, left, used, n, rv)
for rt in right:
if rt:
node.right = TreeNode(rt)
used.add(rt)
backtrack(root, node.right, right, used, n, rv)
used.remove(rt)
if lft:
used.remove(lft)
rv = []
available = list(range(1, n + 1))
for nval in available:
root = node = TreeNode(nval)
used = set([nval])
backtrack(root, node, available, used, n, rv)
return rv
- vscode的完整调试代码
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution(object):
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
def clone(node):
if not node:
return node
nnode = TreeNode(node.val)
nnode.left = clone(node.left)
nnode.right = clone(node.right)
return nnode
def print_tree(root):
rv = []
q = [root]
while len(q):
node = q.pop(0)
if node is None:
rv.append(node)
continue
rv.append(node.val)
q.append(node.left)
q.append(node.right)
print(rv)
def backtrack(root, node, arr, used, n, rv):
if len(used) == n: # 终于把所有点都用光
rv.append(clone(root))
# used = set([root.val])
if root.val == 3:
print("wtf")
left = [a for a in arr if a < node.val] or [None]
right = [a for a in arr if a > node.val] or [None]
for lft in left:
if lft:
node.left = TreeNode(lft)
used.add(lft)
backtrack(root, node.left, left, used, n, rv)
for rt in right:
if rt:
node.right = TreeNode(rt)
used.add(rt)
backtrack(root, node.right, right, used, n, rv)
used.remove(rt)
if lft:
used.remove(lft)
rv = []
available = list(range(1, n + 1))
for nval in available:
root = node = TreeNode(nval)
used = set([nval])
backtrack(root, node, available, used, n, rv)
print("total trees", len(rv))
for r in rv:
print_tree(r)
return rv
if __name__ == "__main__":
s = Solution()
s.generateTrees(4)
- vscode 调试界面
在root已经有3的时候，used里面只有[1,2], 但在上一个frame其实已经出现过[1, 2, 3],下一个frame又被剔除掉了。