JAVA学习-练习试用Java实现“不同的二叉搜索树 II”

问题：

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

示例 1：

输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
示例 2：

输入：n = 1
输出：[[1]]
提示：

1 <= n <= 8

解答思路：

一、题目分析：本题要求生成所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同二叉搜索树。可以使用递归的方法来解决。

二、主要思路：
1. 定义一个辅助函数 'generateTrees'，用于生成所有可能的二叉搜索树。
2. 在 'generateTrees' 函数中，对于每个节点值 i，将其作为根节点，然后递归生成左子树和右子树。
3. 将左子树和右子树的所有可能组合与根节点组合成不同的二叉搜索树。
4. 最后，返回所有生成的二叉搜索树。

三、以下是修改后的代码：

import java.util.ArrayList;
import java.util.List;

public class DifferentBinarySearchTreesII {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new ArrayList<>();
        }
        return generateTrees(1, n);
    }

    private List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> trees = new ArrayList<>();
        if (start > end) {
            trees.add(null);
            return trees;
        }

        for (int i = start; i <= end; i++) {
            List<TreeNode> leftTrees = generateTrees(start, i - 1);
            List<TreeNode> rightTrees = generateTrees(i + 1, end);

            for (TreeNode left : leftTrees) {
                for (TreeNode right : rightTrees) {
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    trees.add(root);
                }
            }
        }

        return trees;
    }

    public static void main(String[] args) {
        DifferentBinarySearchTreesII solution = new DifferentBinarySearchTreesII();
        int n = 3;
        List<TreeNode> trees = solution.generateTrees(n);
        for (TreeNode tree : trees) {
            System.out.println(tree);
        }
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

(文章为作者在学习java过程中的一些个人体会总结和借鉴，如有不当、错误的地方，请各位大佬批评指正，定当努力改正，如有侵权请联系作者删帖。)

原文地址：https://blog.csdn.net/weixin_69763181/article/details/142411761

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！