目录

一，题目描述

英文描述

中文描述

示例与说明

二，解题思路

三，AC代码

Java

四，解题过程

第一博

第二搏

一，题目描述

英文描述

Given an integer n, return all the structurally unique BST's (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.

中文描述

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

示例与说明

1 <= n <= 8

来源：力扣（LeetCode）
链接：力扣
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二，解题思路

参考@力扣官方题解【不同的二叉搜索树 II】

由于线索树节点的取值是1-n，很大程度上简化了该题的难度。直接上代码

三，AC代码

Java

class Solution {
    public List build (int start, int end) {
        List allTrees = new ArrayList<>();
        if (start > end) {
            allTrees.add(null);// !!!这里不添加null，直接返回allTrees会报错。。。
            return allTrees;
        }
        for (int i = start; i <= end; i++) {
            List leftTrees = build(start, i - 1);// 获得所有的左子树节点
            List rightTrees = build(i + 1, end);// 获得所有的右子树节点
            for (TreeNode left : leftTrees) {
                for (TreeNode right : rightTrees) {
                    TreeNode head = new TreeNode(i);// 构建搜索树
                    head.left = left;
                    head.right = right;
                    allTrees.add(head);
                }
            }
        }
        return allTrees;
    }
    public List generateTrees(int n) {
        if (n == 0) return null;
        List ans = build(1, n);
        return ans;
    }
}

四，解题过程

第一博

第一眼看上去就感觉要用递归，但是具体怎么构建搜索树没有头绪。。。

第二搏

本来以为递归自己已经掌握的很熟练了，这道题狠狠的打了我的脸。。。

递归的核心思想就是将原来的问题抽象成子问题的集合。

针对这一题来说。虽然第一眼就知道要用递归来实现，但却陷入了太多的细节之中，比如

• 如何判断哪个数字被遍历过、
• 怎样在构建线索树的同时记录树的根节点、
• 怎样定位下一个要遍历的数字、
• 生成的线索树如何避免重复等等

这样一来，编写的程序就显得极为复杂。

其实上面思路产生的原因就是忘记了递归最核心的功能。

假如这个函数能产生正确的线索树，那么当前节点的左右子树不就出来了吗？需要做的仅仅是将他们拼接到当前节点的左右子树部分。

剩下的问题就是如何确定当前节点的值，以及递归方法需要的参数。

• 确定当前节点的值：可能的取值范围内逐个遍历；
• 递归方法需要的参数：可能的取值范围，即左右边界；

 

看了官方题解之后，自己做就简单多了。除了一个小细节。。。