leetcode-95 Unique Binary Search Trees II

Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.

Example:

Input: 3 Output: [   [1,null,3,2],   [3,2,null,1],   [3,1,null,null,2],   [2,1,3],   [1,null,2,null,3] ] Explanation: The above output corresponds to the 5 unique BST's shown below: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3

 

解题方法：遍历所有的根节点，将其分为左右节点，为其左右节点进行遍历判断结果

    public List<TreeNode> generateTrees(int n) {         if(n<=0) {             return new ArrayList<>();         }         return getRes(1,n);         }               public List<TreeNode> getRes( int begin,int end) {         List<TreeNode> res = new ArrayList<>();         if (begin > end) {             return null;         }         for (int i = begin; i <= end; i++) {             List<TreeNode> left = getRes(begin, i - 1);             List<TreeNode> right = getRes(i + 1, end);                     if (left != null && right != null) {                 for (TreeNode l : left) {                     for (TreeNode r : right) {                         TreeNode now = new TreeNode(i);                         now.left = l;                         now.right = r;                         res.add(now);                     }                 }             } else if (left != null) {                 for (TreeNode l : left) {                     TreeNode now = new TreeNode(i);                     now.left = l;                     res.add(now);                 }             } else if (right != null) {                 for (TreeNode r : right) {                     TreeNode now = new TreeNode(i);                     now.right = r;                     res.add(now);                 }             }else {                 TreeNode now = new TreeNode(i);                 res.add(now);             }         }         return res;     }