每天一道Rust-LeetCode，2019-06-06

坚持每天一道题,刷题学习Rust.

原题

题目描述

示例:

输入: 3

输出: 5

解释:

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

1 3 3 2 1

\ / / / \

3 2 1 1 3 2

/ / \

2 1 2 3

解题过程

思路:

搜索树的特点就是左小右大

因此:

这是一个纯计算的过程,都不用模拟二叉树

1...n

G[i]表示有i个节点的二叉树有多少种

G[N]=G[0]G[N-1]+G[1]G[N-2]+G[2]*[N-3]+....

考虑1做定点的情况主要考虑右边N-1个节点的各种组合怎么挂在1的右子树

考虑2做顶点的情况,左边是一个节点的子树,右边是n-2个节点的子树

两个总数相乘就是所有可能的组合.

struct Solution {}
impl Solution {
    pub fn num_trees(n: i32) -> i32 {
        if n <= 1 {
            return n;
        }
        let mut v = vec![0; (n + 1) as usize];
        v[0] = 1;
        v[1] = 1;
        return Solution::num_trees_internal(n as usize, &mut v);
    }
    pub fn num_trees_internal(n: usize, v: &mut Vec<i32>) -> i32 {
        if v[n] > 0 {
            return v[n];
        }
        let mut sum = 0;
        for i in 0..n {
            v[i] = Solution::num_trees_internal(i, v);
            v[n - i - 1] = Solution::num_trees_internal(n - i - 1, v);
            sum += v[i] * v[n - i - 1];
        }
        sum
    }
}
#[cfg(test)]
mod test {
    use super::*;
    #[test]
    fn test_num_trees() {
        assert_eq!(1, Solution::num_trees(1));
        assert_eq!(2, Solution::num_trees(2));
        assert_eq!(5, Solution::num_trees(3));
    }
}

一点感悟

动态规划是自底向上,针对这种情况非常简单,记录下来,避免反复计算.

其他

欢迎关注我的github,本项目文章所有代码都可以找到.