Leetcode의 독특한 바이너리 Search Tree I

1254 단어
Topic: 반복 + DP
Question:
Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.
For example, Given n = 3, your program should return all 5 unique BST's shown below.
   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

confused what  "{1,#,2,3}"  means? > read more on how binary tree is serialized on OJ. » Solve this problem
방법:
방법은 Fibonacci의 처리와 같다.
Code:
// 
public class Solution {
    public int numTrees(int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int sum = 0;
        if(n == 0 || n == 1) return 1;
        else
            for(int i=0; i

소결:
이 문제의 난점은 점차적으로 무엇을 하고 있는지, 이전에 산출된 노드와basecase를 어떻게 이용하여 필요한 결과를 구하는지에 있다.팁: 루트 결과 = 썸(왼쪽 하위 트리 결과 * 오른쪽 하위 트리 결과).

좋은 웹페이지 즐겨찾기