题目链接 : 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

思路:

二叉搜索树, 一节点大于左子树节点, 小于右子树节点

所以我们节点是从1n,当一个节点为val那么它的左边是< val,右边是>val,

我们用递归解决!

代码:

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
import functools
class Solution:
def generateTrees(self, n: int) -> List[TreeNode]:
if n == 0: return []
@functools.lru_cache(None)
def helper(start, end):
res = []
if start > end:
res.append(None)
for val in range(start, end + 1):
for left in helper(start, val - 1):
for right in helper(val + 1, end):
root = TreeNode(val)
root.left = left
root.right = right
res.append(root)
return res return helper(1, n)

java

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<TreeNode> generateTrees(int n) { if (n == 0) return new ArrayList<>();
return helper(1, n); } private List<TreeNode> helper(int start, int end) {
List<TreeNode> res = new ArrayList<>();
if (start > end) {
res.add(null);
return res;
}
for (int val = start; val <= end; val++) {
List<TreeNode> left = helper(start, val - 1);
List<TreeNode> right = helper(val + 1, end);
for (TreeNode l : left) {
for (TreeNode r : right) {
TreeNode root = new TreeNode(val);
root.left = l;
root.right = r;
res.add(root);
}
}
}
return res;
}
}
05-11 22:15
查看更多