1. 概述

给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。

示例：

输入：3

输出：

[

[1,null,3,2],

[3,2,null,1],

[3,1,null,null,2],

[2,1,3],

[1,null,2,null,3]

]

解释：

以上的输出对应以下 5 种不同结构的二叉搜索树：

1 3 3 2 1

\       /     /      / \      \
 3     2     1      1   3      2
/     /       \                 \

2 1 2 3

提示：

0 <= n <= 8

2. 解题

<?php


class TreeNode
{
    public $val = NULL;
    /** @var TreeNode */
    public $left = NULL;
    /** @var TreeNode */
    public $right = NULL;

    function __construct($val = 0, $left = NULL, $right = NULL)
    {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

class Solution
{
    private $ret = [];

    /**
     * @param Integer $n
     * @return TreeNode[]
     */
    public function generateTrees($n)
    {
        $this->do($n);
    }

    /**
     * @param int $n
     * @param int $number
     * @param TreeNode $node
     */
    private function do(int $n, $number = 1, $node = NULL)
    {
        if ($number == $n) {
            $this->ret[] = $node;
            return;
        }

        for ($i = $number; $i < $n; $i++) {
            if ($node == NULL) {
                $node = new TreeNode($number);
                $this->do($n, $i, $node);
            } elseif ($node->left)

                $tmpLeftVal =
                $tmpLeft = new TreeNode($tmpLeftVal);
        }
    }

    private function addNextNode(TreeNode $headNode, TreeNode $newNode)
    {

    }

    private function _addNextNode(TreeNode $headNode, TreeNode $newNode)
    {
        if ($newNode == NULL) {
            return $headNode;
        }

        if ($headNode == NULL) {
            $headNode = $newNode;
            return $headNode;
        }

        $headNode->left = $this->_addNextNode($headNode->left, $newNode);
        $headNode->right = $this->_addNextNode($headNode->right, $newNode);
        return $headNode;
    }
}

$n = 3;
$cls = new Solution();
$ret = $cls->generateTrees($n);
print_r($ret);