手机怎么做自己的网站,wordpress 主题吧,如何做淘宝联盟网站主,济南卓远网站建设公司给定一个整数 n#xff0c;生成所有由 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 种不同结构的二叉搜索树#xff1a; 1 3 …给定一个整数 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
思路枚举每个root和对应的左右子树情况然后组合即可。
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {public LinkedListTreeNode generate_trees(int start, int end) {LinkedListTreeNode all_trees new LinkedListTreeNode();if (start end) {all_trees.add(null);return all_trees;}//枚举所有rootfor (int i start; i end; i) {// 枚举左子树所有情况LinkedListTreeNode left_trees generate_trees(start, i - 1);// 枚举右子树所有情况LinkedListTreeNode right_trees generate_trees(i 1, end);// 连接起来的所有情况for (TreeNode l : left_trees) {for (TreeNode r : right_trees) {TreeNode current_tree new TreeNode(i);current_tree.left l;current_tree.right r;all_trees.add(current_tree);}}}return all_trees;}public ListTreeNode generateTrees(int n) {if (n 0) return new LinkedListTreeNode();return generate_trees(1, n);}
}
