Swift solution - recursive


  • 0
    class Solution {
        func generateTrees(_ n: Int) -> [TreeNode?] {
            if n <= 0 {
                return []
            }
            return generateSubtrees(1, n)
        }
        
        private func generateSubtrees(_ start: Int, _ end: Int) -> [TreeNode?] {
            
            if start > end {
                return [nil]
            }
            
            if start == end {
                return [TreeNode(start)]
            }
            
            var result = [TreeNode?]()
            var leftSubtrees = [TreeNode?]()
            var rightSubtrees = [TreeNode?]()
            
            for i in start...end {
                leftSubtrees = generateSubtrees(start, i - 1)
                rightSubtrees = generateSubtrees(i + 1, end)
                
                for left in leftSubtrees {
                    for right in rightSubtrees {
                        let root = TreeNode(i)
                        root.left = left
                        root.right = right
                        result.append(root)
                    }
                }
            }
            
            return result
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.