Description

LeetCode 95

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.

Example:

Input: 3
Output:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Analysis

When I first see this problem, because the problem tells us to list all the conditions, I tend to use backtracking. However, it is a bad idea. But it tells me a condition that backtracking does not work.

Considering about the problem, the objective binary search trees could be classified into different classes by the value of root. If the value is the smallest number of the valid number, then it only has right subtree. We could change the valid number domain and implement the process to its right subtree recursively. If the value is the largest number of the valid number, so as the left subtree. But if the value is less than the largest number and larger than the smallest number, we must implement the process to the left subtree and right subtree at the same time. We must judge if the binary search tree has been constructed. And the terminal condition is relation to the binary search tree. We can’t do backtracking between the construction of left subtree and right subtree because if the one of the subtree’s construction is cancelled we cannot judge the merged binary search tree. The backtracking method will become very complex because of this process.

There is another one easy method that should be understood. It is like divide-and-conquer. In this method, we just use the list of binary search tree to deliver the result. First classify the binary search tree by the root. Then implement the process to the left subtree and right subtree recursively to get a tree node list of left subtree and right subtree. Then merge the two lists and return the result. The merging process is to use all the combinations of the list of left subtree and the list of right subtree as the left subtree and the right subtree.

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> res=new ArrayList<>();
        List<TreeNode> tmp;
        for(int i=1;i<=n;i++)
        {
            tmp=helper(new TreeNode(i),1,n);
            for(int j=0;j<tmp.size();j++)
            {
                res.add(tmp.get(j));
            }
        }
        return res;
    }
    public List<TreeNode> helper(TreeNode root,int start,int end)
    {
        if(start==end) 
        {
            List<TreeNode> res=new ArrayList<>();
            res.add(new TreeNode(root.val));
            return res;
        }
        TreeNode tmp;
        List<TreeNode> mergelist=new ArrayList<>();
        if(root.val==start)
        {
            for(int i=start+1;i<=end;i++)
            {
                root.right=new TreeNode(i);
                List<TreeNode> rightlist=helper(root.right,start+1,end);
                for(int j=0;j<rightlist.size();j++)
                {
                    mergelist.add(new TreeNode(root.val));
                    tmp=mergelist.get(mergelist.size()-1);
                    tmp.right=rightlist.get(j);
                }
            }
        }
        else if(root.val==end)
        {
            for(int i=start;i<=end-1;i++)
            {
                root.left=new TreeNode(i);
                List<TreeNode> leftlist=helper(root.left,start,end-1);
                for(int j=0;j<leftlist.size();j++)
                {
                    mergelist.add(new TreeNode(root.val));
                    tmp=mergelist.get(mergelist.size()-1);
                    tmp.left=leftlist.get(j);
                }                
            }            
        }
        else
        {
            for(int m=start;m<=root.val-1;m++)
            {
                for(int n=root.val+1;n<=end;n++)
                {
                    root.left=new TreeNode(m);
                    root.right=new TreeNode(n);
                    List<TreeNode> leftlist=helper(root.left,start,root.val-1);
                    List<TreeNode> rightlist=helper(root.right,root.val+1,end);
                    for(int i=0;i<leftlist.size();i++)
                    {
                        for(int j=0;j<rightlist.size();j++)
                        {
                            mergelist.add(new TreeNode(root.val));
                            tmp=mergelist.get(mergelist.size()-1);
                            tmp.left=leftlist.get(i);
                            tmp.right=rightlist.get(j);
                        }
                    }
                }
            }
        }
        return mergelist;
    }
}

Reference

[1] https://www.geeksforgeeks.org/construct-all-possible-bsts-for-keys-1-to-n/

 

Leave a Reply

Your email address will not be published. Required fields are marked *