【改造后序遍历算法】95. 不同的二叉搜索树 II

95. 不同的二叉搜索树 II

解题思路

• 遍历每一个节点
• 查看以k为根节点的二叉搜索树
• 储存所有左子树的根节点
• 储存所有右子树的根节点
• 将左子树和右子树组装起来 将根节点储存在向量中

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<TreeNode> generateTrees(int n) {if(n < 1) return generate(1,0);return generate(1,n);}List<TreeNode> generate(int start,int end){List<TreeNode> subTree = new ArrayList<>();// 储存所有的根节点if(start > end){subTree.add(null);return subTree;}// 查找以k为根节点的二叉搜索树for(int k = start; k <= end; k++){// 储存所有左子树的根节点List<TreeNode> left = generate(start,k - 1);// 储存所有右子树的根节点List<TreeNode> right = generate(k + 1,end);// 将左子树和右子树组装起来  将根节点储存在向量中for(int i = 0; i < left.size(); i++){for(int j = 0; j < right.size(); j++){TreeNode root = new TreeNode(k);// 新建一个节点root.left = left.get(i);root.right = right.get(j);subTree.add(root);}}}return subTree;}
}