leetcode做题记录 —— unique-binary-search-trees-ii

unique-binary-search-trees-ii 
Given an integer 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.   1         3     3      2      1
2.    \       /     /      / \      \
3.     3     2     1      1   3      2
4.    /     /       \                 \
5.   2     1         2                 3

unique-binary-search-trees-ii

求 n 个节点的所有搜索二叉树 
比如，n = 3 的时候，总共有5总不同的结构，返回一个包含这 5 棵树的数组

1.   1         3     3      2      1
2.    \       /     /      / \      \
3.     3     2     1      1   3      2
4.    /     /       \                 \
5.   2     1         2                 3

参考来源

解法

• 遍历start ~ end 之间的所有值作为根，比如设为 i 
  
  • start ~ i - 1 之间的值即为根为 i 的左子树所包含的值，递归获取这个区间的所有子树
  • i + 1 ~ end 之间的值即为根为 i 的右子树所包含的值，递归获取这个区间的所有子树
  • 遍历所有子树的组合，以 i 为根结合在一起
  • 返回构造好的数组

1.//Javascript
2./**
3. * Definition for a binary tree node.
4. * function TreeNode(val) {
5. *     this.val = val;
6. *     this.left = this.right = null;
7. * }
8. */
9./**
10. * @param {number} n
11. * @return {TreeNode[]}
12. */
13.
14.var generateTrees = function(n) {
15.    return n === 0 ? [] : generateFrom(1, n);
16.};
17.var generateFrom = function(start, end) {
18.    if( start > end )
19.    {
20.        return [null];
21.    }
22.    let res = [];
23.    for( let i = start; i <= end; i++)
24.    {
25.        let leftTrees = generateFrom(start, i - 1);
26.        let rightTrees = generateFrom(i + 1, end);
27.        for( let l = 0; l < leftTrees.length; l++ )
28.        {
29.            for( let r = 0; r < rightTrees.length; r++ )
30.            {
31.                let root = new TreeNode(i);
32.                root.left = leftTrees[l];
33.                root.right = rightTrees[r];
34.                res.push(root);
35.            }
36.        }
37.    }
38.    return res;
39.}

End