מריה בוטוסוב

נתון מספר n. יש להחזיר רשימה של כל העצים שניתן לבנות ממספרים 1...n

1. כל מספר מ1 עד n יכול להיות root בעץ חיפוש בינארי

2. כאשר אנחנו בוחרים מספר k מתוך 1..n מספרים כ root - כל המספרים קטנים מ k יהיה מצד שמאל של root, וכל הגדולים מצד ימין.

3. אפשר להגיד שעץ מורכב מתת עצים - לכן פתרון רקורסיבי יהיה הכי פשוט להבנה.

public List<TreeNode> generateTrees(int n) {
    return genTreeList(1, n);
}
 
private List<TreeNode> genTreeList(int start, int end) {
    List<TreeNode> list = new List<TreeNode>();
    if(start > end) 
        list.Add(null);
        
    for(int i = start; i<=end; i++) {
        List<TreeNode> leftList = genTreeList(start, i-1);
        List<TreeNode> rightList = genTreeList(i+1, end);
        foreach(TreeNode left in leftList){
            foreach(TreeNode right in rightList) {
                TreeNode root = new TreeNode(i);
                root.left = left;
                root.right = right;
                list.Add(root);
            }
        }
    }
    
    return list;
}