95. Unique Binary Search Trees I

题目

给定一个整数 n， 返回由数字 1 到 n 个节点组成的所有可能的二叉搜索树。

解析

这个题目属于 96 题的进阶版本，根据 96 题，由 1 到 n 组成的二叉搜索树可以递归为 以 k 节点为根节点，以 1～k-1 为左子树，k+1 ~ n 为右子树的组合。其中 k 取值为 1 到 n。

f(1,1) = nil-f(1,1)-nil
f(1,2) = nil-1-f(2,2) + f(1,1)-2-nil
f(1,3) = nil-1-f(2,3) + f(1,1)-2-f(3,3) + f(1,2)-3-nil
...
f(1,n) = nil-1-f(2,n) + f(1,k-1)-k-f(k+1,n) + f(1,n-1)-n-nil

同样的为了逻辑方便，我们构造两个虚拟节点
f(1,0) = nil
f(n+1,n) = nil

上式改写后为 f(1,n) =f(1,k-1) ~ k ~f(k+1,n) 1<=k=n
递归函数原型为 f(i,j int) []*TreeNode

伪代码

for k:=i;k<=j;k++
  lefts = f(i,k-1)
  rights = f(k+1,j)
for m<lefts.len
  for n<rights.len
    node = new(k)
    node.left = lefts[m]
    node.right = rights[n]
    append(rst, node)
return rst

代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func generateTrees(n int) []*TreeNode {
    return f(1,n)
}

func f(i,j int) []*TreeNode {
    var rsts []*TreeNode
    if i>j {
        return []*TreeNode{nil}
    }
    for k:=i;k<=j;k++ {
        lefts := f(i, k-1)
        rights := f(k+1, j)
        rst := make([]*TreeNode, len(lefts)*len(rights))
        for m := range lefts {
            for n := range rights {
                node := &TreeNode{Val: k}
                node.Left = lefts[m]
                node.Right = rights[n]
                rst[m*len(rights)+n] = node
            }
        }
        rsts=append(rsts, rst...)
    }
    return rsts
}

image.png

这个代码在递归的过程中，会重复计算f(i,j) 的可能值，可以将其转化为非递归实现。