刷算法-- leetcode 96. 不同的二叉搜索树

2023-12-29 14:02:53

在这里插入图片描述

思路

  1. 观察树的组成,可以发现n=3时的二叉搜索树可以由,头节点分别为1、2、3时的所有结果组成!
  2. 定义dp[i]为由i个节点组成的二叉搜索树的个数。
  3. 确定递推公式,dp[i] = 由1为头节点组成的二叉搜索树个数+由2为头组成的个数+…+由i为头节点组成的个数。
    所以,进一步分析:
    1. 由1为头节点组成的二叉搜索树个数=左子树个数为0时搜索树个数*右子树节点数为2时的搜索树个数.
    2. 由2为头节点时组成的搜索树个数=左子树包含1个节点是的搜索树个数*右子树节点数为2时的搜索树个数
      节点数量为2时的搜索树个数=dp[2]
      节点数量为1时的搜索树个数=dp[1]
  4. 所以,dp[3] = dp[0]*dp[2] + dp[1]*dp[1] + dp[2]*dp[0];
  5. 可以看出上述公式是一种交错的关系。使用双重循环去递推。

文章来源:https://blog.csdn.net/weixin_46050018/article/details/135288074
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。