力扣题95：不同的二叉搜索树 II

Question

力扣题95. 不同的二叉搜索树 II

我的问题：
感觉思路没完全错，但是对于分别寻找左右子树的2个for循环不确定这样写对不对；copy函数是为了在原来的搜索树上修改，通过回溯找到新的可行的树，但是这样应该会产生多余的节点没法free掉，感觉这样写不对不知道怎么改。

我的代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
struct TreeNode *copy(struct TreeNode *oldroot)
{
    if(oldroot==NULL)
        return;
    struct TreeNode *newroot=(struct TreeNode*)malloc(sizeof(struct TreeNode));
    newroot->val=oldroot->val;
    newroot->left=copy(oldroot->left);
    newroot->right=copy(oldroot->right);
    return newroot;
}

void create(struct TreeNode **res,struct TreeNode *root,int i,int il,int ir,int *res_num,int temp_num,int n)
{
    root=(struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val=i;
    root->left=root->right=NULL;
    temp_num++;
    if(temp_num==n)
    {
        res[++(*res_num)]=copy(res[*res_num]);
        return;
    }
    for(int j=i-1;j>=il;j--)
    {
        create(res,root->left,j,il,j,res_num,temp_num,n);
    }
    for(int j=i+1;j<=ir;j++)
    {
        create(res,root->right,j,j,ir,res_num,temp_num,n);
    }
}


struct TreeNode** generateTrees(int n, int* returnSize){
    struct TreeNode **res=(struct TreeNode**)malloc(sizeof(struct TreeNode*)*100);
    int res_num=0;
    int temp_num=0;
    int il=1,ir=n;
    for(int i=1;i<=n;i++)
    {
        struct TreeNode* root;
        res[res_num]=root;
        create(res,root,i,il,ir,&res_num,temp_num,n);
        res_num++;
    }
    *returnSize=res_num;
    return res;
}

Answer 1

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 以下回答来自chatgpt:

  对于力扣题95不同的二叉搜索树 II的问题： 首先，关于寻找左右子树的2个for循环的写法不确定是否正确，需要看具体代码才能判断是否正确。但是一般情况下，对于二叉搜索树而言，寻找左右子树的写法类似于以下代码：

  def generateTrees(n: int) -> List[TreeNode]: def generate(l, r): if l > r: return [None,] ans = [] for i in range(l, r+1): left_nodes = generate(l, i-1) right_nodes = generate(i+1, r) for left in left_nodes: for right in right_nodes: temp_node = TreeNode(i) temp_node.left = left temp_node.right = right ans.append(temp_node) return ans

  if n == 0:
      return []
  return generate(1, n)
  

  这种写法的思路是分别寻找每个数字作为根节点时左右子树可能的组合情况，然后进行遍历。具体来说，对于数字i，它的左子树可能包含从l到i-1的任何数字，右子树可能包含从i+1到r的任何数字。那么，我们只需要分别枚举左子树和右子树中可能包含的数字进行组合，然后将所有组合结果组合起来即可。

  其次，对于使用copy函数在原始搜索树上进行修改，可能会导致产生多余的节点无法free掉的问题，可以使用递归函数进行解决。具体来说，我们可以定义一个递归函数，每次传入左边界le和右边界ri，然后分别对于在这个区间范围内的数字进行枚举，将数字作为根节点，分别枚举可能的左子树和右子树，然后递归调用函数，将左右子树的根节点插入到根节点的左右子树中。最后，返回根节点即可。具体代码如下：

  class Solution: def generateTrees(self, n: int) -> List[TreeNode]: def dfs(le, ri): if le > ri: return [None,] ans = [] for i in range(le, ri+1): left_nodes = dfs(le, i-1) right_nodes = dfs(i+1, ri) for left in left_nodes: for right in right_nodes: root = TreeNode(i) root.left = left root.right = right ans.append(root) return ans

      if n == 0:
          return []
      return dfs(1, n)
  

  最后，需要注意的是，由于需要生成多个搜索树，我们需要返回一个列表而不是单个根节点节点。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^