package main

import (
	"fmt"
)

func main() {
 fmt.Println(generateTrees(3)[0].Right.Right.Right)
}

func generateTrees(n int) []*TreeNode {
	if n == 0 {
		return nil
	}
	return depth(1,n)
}

func depth(start , end int ) []*TreeNode {
	if start > end {
		return [] *TreeNode{nil}
	}
	var TreeNodes []*TreeNode
	//枚举所有可行根节点
	for i := start ; i <= end ; i++ {
		left := depth(start,i-1)
		right := depth(i+1 , end)
		//左子树和右子树
		for _ , Left := range left {
			for _ , Right := range right {
				currentree := TreeNode{Val: start}
				currentree.Left , currentree.Right = Left , Right
				TreeNodes = append(TreeNodes, &currentree)
			}
		}
	}
	return TreeNodes
}





type TreeNode struct {
	Val int
	Left *TreeNode
	Right *TreeNode
}

//func generateTrees(n int) []*TreeNode {
//	/*思路：创建数组，用for循环递归遍历，记录当前根节点所用的数组下标，循环加入根节点左边的数字和右边的数字，当层数等于n时，返回node*/
//	res := make([]*TreeNode,0)
//	arr := make([]int,n)
//	//1.初始化数组
//	for i := range arr {
//		arr[i] = i +1
//	}
//	//2.for循环递归遍历，外层是根节点
//	for i := 0 ; i < n ; i++ {
//		node := TreeNode{Val: arr[i]}
//		/*parame 1.根节点 2.数组 3.层数 , 组装二叉树*/
//		node.Left  = depth( arr, n-1 , i )
//		node.Right = depth(arr,n +1 , i)
//		res  = append(res, &node)
//	}
//
//
//	return res
//}
//
//func depth( node  *TreeNode ,  arr []int , n , index int) *TreeNode {
//	if index < 0 || index > n -1 {
//		return nil
//	}
//	for i:=0 ; i < n ; i++ {
//		if i < index {
//			node.Left = depth()
//		}
//	}