专栏首页健程之道力扣96——不同的二叉搜索树

力扣96——不同的二叉搜索树

原题

给定一个整数 n,求以 1 ... n 为节点组成的二叉搜索树有多少种?

示例:

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2     1
    \        /     /      / \      \
    3      2     1     1   3      2
    /      /       \                    \
   2     1         2                    3

原题url:https://leetcode-cn.com/problems/unique-binary-search-trees/

解题

这道题看到的第一眼,就和之前的格雷编码一样,又想用动态规划,每次都是遍历所有情况去检查是否有效,但感觉时间复杂度会很高,找找看有没有什么更高效的做法。

所谓高效,也就是寻找规律了,最好的是可以递推,下一次运算可以利用之前的结果,而本题就是用这种规律的。我们来试试 n 等于0、1、2、3的情况:

n = 0,只有1种。

n = 1,也只有1种。

n = 2,有2种
1           2
 \         /
   2    1

n = 3,有5种
   1         3     3      2     1
    \        /     /      / \      \
    3      2     1     1   3      2
    /      /       \                    \
   2     1         2                    3

让我们回想一下什么叫二叉搜索树,就是针对每个节点,其左子树中所有节点都比它小,其右子树中所有节点都比它大。

再想一下,如果我们针对根选中的情况下,左右子树节点的个数其实也已经定下来了,那么假设同样是 3 个节点,"1、2、3"和"4、5、6"可以组成二叉搜索树,从数量上讲是一样的,因为大小关系没有变。

因此,我们可以说,针对二叉搜索树,其不用考虑值具体是多少,只需要考虑其大小关系即可,那么这就符合上面我所希望的场景了,下一次的运算可以利用之前的结果。

以这道题来说,其具体规律就是:

  1. 从 1 开始遍历直至 n,以每个节点作为根节点,这样就能计算出左右各个子树的所有节点数。
  2. 当我们知道了个数,也就可以利用之前计算的结果,获得左右子树可能的情况,两者相乘,也就是在当前根的情况,所有二叉搜索树的情况。
  3. 将所有根节点的总计算出的数量做累加,也就得出了当前节点数的总情况。

让我们看看代码:

class Solution {
    public int numTrees(int n) {
            // 存放中间结果
        int[] result = new int[n + 1];
        result[0] = 1;
        result[1] = 1;

        for (int i = 2; i <= n; i++) {
            int count = 0;
            for (int j = 1; j <= i; j++) {
                // 左子树总节点数 + 右子树总节点数
                count += (result[j - 1] * result[i - j]);
            }
            result[i] = count;
        }

        return result[n];
    }
}

提交OK, 执行用时:0 ms,内存消耗:33.2 MB

总结

以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题目只要利用规律,构造递推关系,也就能解决了。

本文分享自微信公众号 - 健程之道(JianJianCoder),作者:健健壮

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-01-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 力扣 1519——子树中标签相同的节点数

    本题主要在于对树这种数据结构的考察,以及深度优先遍历的使用,优化时可以采取空间换时间的策略。

    健程之道
  • 剑指offer 13——机器人的运动范围

    地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(...

    健程之道
  • 力扣105——从前序与中序遍历序列构造二叉树

    原题url:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-i...

    健程之道
  • kubernetes从懵圈到熟练 – 集群伸缩原理

    阿里云K8S集群的一个重要特性,是集群的节点可以动态的增加或减少。有了这个特性,集群才能在计算资源不足的情况下扩容新的节点,同时也可以在资源利用率降低的时候,释...

    kubernetes中文社区
  • 一文搞定 Redis 复制(全会的举个手看看)

    Step 2:从节点只是保存了 slaveof 命令中主节点的信息,并没有立即发起复制。

    良月柒
  • 江苏省初中信息技术八年级 -张叔叔一文读懂

    今天张叔叔给大家讲讲江苏省八年级信息技术教材内容,之前的七年级教材讲解收到了热烈欢迎,在此感谢所有的读者们,也希望大家积极转载,为社会主义建设添砖加瓦!

    张叔叔讲互联网
  • 【计算机本科补全计划】图的连通性check by 并查集Union Find

    具体的想法来自一篇写的超好的博客,如果底子不是很好,建议看下面这篇,当然如果可以给我顺手点个赞就更好了!!

    用户1687088
  • 数据结构与算法(十二) 红黑树

    •节点是有颜色的Red/Black•根节点必须是Black•叶子节点必须是Black•红黑树的叶子节点会自动将度为0 或者度为1的节点的度自动补充为2,补充的节...

    老沙
  • Gossip 协议详解

    Gossip protocol 也叫 Epidemic Protocol (流行病协议)。Gossip protocol在1987年8月由施乐-帕洛阿尔托研究中...

    江帅帅
  • 分布式架构——Gossip 协议详解

    Gossip protocol 也叫 Epidemic Protocol (流行病协议)。Gossip protocol在1987年8月由施乐-帕洛阿尔托研究中...

    孙玄@奈学教育

扫码关注云+社区

领取腾讯云代金券