I find most AC solutions on forum are actually wrong. Here is the correct one


  • 0

    solutions such as https://leetcode.com/discuss/33003/java-recursive-solution-straight-forward
    is accepted by OJ. However, I find a problem with it. The structure of the tree is bad. It uses multiply root nodes of different trees pointing to the same substree object. So if we modify one of the trees of output list, the other trees will be affected. We need a deep copy of every tree node. Different trees cannot share common components. That's why I use a cloneTree() to deep copy every node instead of just pointing to the same subtree component.

    public class Solution {
        public List<TreeNode> generateTrees(int n) {
            if (n == 0) {
                return new ArrayList<>();
            }
            return generateTreesHelper(1, n);
        }
        
        private List<TreeNode> generateTreesHelper(int start, int end) {
            List<TreeNode> uniqueTrees = new ArrayList<>();
            if (start > end) {
                uniqueTrees.add(null);
                return uniqueTrees;
            } 
            TreeNode root;
            List<TreeNode> leftSubtrees, rightSubtrees;
            for (int i = start; i <= end; i++) {
                leftSubtrees = generateTreesHelper(start, i - 1);
                rightSubtrees = generateTreesHelper(i + 1, end);
                for (TreeNode leftSubtree : leftSubtrees) {
                    for (TreeNode rightSubtree : rightSubtrees) {
                        root = new TreeNode(i);
                        root.left = cloneTree(leftSubtree); // must make a copy
                        root.right = cloneTree(rightSubtree); // for each different tree
                        uniqueTrees.add(root);
                    }
                }
            }
            return uniqueTrees;
        }
        
        private TreeNode cloneTree(TreeNode root) {
            if (root == null) {
                return null;
            }
            TreeNode newRoot = new TreeNode(root.val);
            newRoot.left = cloneTree(root.left);
            newRoot.right = cloneTree(root.right);
            return newRoot;
        }
    }

  • 0
    C

    your understanding is incorrect. If you don't believe that, you can play in the local IDE and see. (The original post is correct, see discussion below.)


  • 0

    Every root node is brand new, but left and right subtrees are reused.


  • 0
    C

    Think about this: if every root node is brand new, how about the roots of the subtrees?


  • 0

    You see the double loop there? That is where you start reusing the subtrees.
    For different root new just created, you reuse the left subtree in the loop.


  • 0

    I know you mean the recursion. But actually there is no recursion for the subtrees. They have been already placed in the list. All you did is pointing different roots to the same subtrees


  • 0
    C

    Yes, you are correct. I see your point. Let's say we have nl left subtrees, nr right subtrees. We create nl X nr distinct roots to represent nl X nr trees.


Log in to reply
 

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