using C#


  • 0
    P
    
    public class Solution {
            public IList<TreeNode> GenerateTrees(int n)
            {
                int[] memo = new int[n + 1];
                IList<TreeNode> trees = new List<TreeNode>();
                return this.GenerateSubTrees(1, n, memo);
            }
    
            private IList<TreeNode> GenerateSubTrees(int startNum, int endNum, int[] memo)
            {
                if (startNum > endNum)
                {
                    return new List<TreeNode>();
                }
    
                IList<TreeNode> trees = new List<TreeNode>();
                for (int iter = startNum; iter <= endNum; iter++)
                {
                    IList<TreeNode> leftSubTrees = this.GenerateSubTrees(startNum, iter - 1, memo);
                    
                    IList<TreeNode> rightSubTrees = this.GenerateSubTrees(iter + 1, endNum, memo);
    
                    if (leftSubTrees.Count == 0 && rightSubTrees.Count == 0)
                    {
                        TreeNode root = new TreeNode(iter);
                        trees.Add(root);
                    }
                    if (leftSubTrees.Count == 0)
                    {
                        foreach (TreeNode rightSubTree in rightSubTrees)
                        {
                            TreeNode root = new TreeNode(iter);
                            root.right = rightSubTree;
                            trees.Add(root);
                        }
                    }
                    else if (rightSubTrees.Count == 0)
                    {
                        foreach (TreeNode leftSubTree in leftSubTrees)
                        {
                            TreeNode root = new TreeNode(iter);
                            root.left = leftSubTree;
                            trees.Add(root);
                        }
                    }
                    else
                    {
                        foreach (TreeNode leftSubTree in leftSubTrees)
                        {
                            foreach (TreeNode rightSubTree in rightSubTrees)
                            {
                                TreeNode root = new TreeNode(iter);
                                root.left = leftSubTree;
                                root.right = rightSubTree;
                                trees.Add(root);
                            }
                        }
                    }
                }
    
                return trees;
            }
    }
    

Log in to reply
 

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