95. Unique Binary Search Trees II

Link

Solution

有點DP的概念，針對每個node當root的狀況分成 左子樹[1... i-1], 右子樹[i+1 ... n ]的方式遞迴下去處理

如果能將問題從單一個輸入ex. N，變成範圍 ( 1~N) 那或許是個可能的好方式去處理遞迴問題。

class Solution {
    public List<TreeNode> generateTrees(int n) {
        if(n == 0)
            return new ArrayList<>();
        return helper(1, n);
    }
    
    public List<TreeNode> helper(int start, int end){
        List<TreeNode> ret = new ArrayList<>();
        if(end < start) ret.add(null);
        for(int i = start ; i <= end; i++){
            List<TreeNode> leftTrees = helper(start, i-1);
            List<TreeNode> rightTrees = helper(i+1, end);
            for(TreeNode leftTree : leftTrees){
                for(TreeNode rightTree : rightTrees){
                    TreeNode root = new TreeNode(i);
                    root.left = leftTree;
                    root.right = rightTree;
                    ret.add(root);
                }
            }
        }
        return ret;
    }
}