Question

Formatted question description: https://leetcode.ca/all/95.html

95	Unique Binary Search Trees II

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

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

@tag-tree
@tag-divideconquer

Algorithm

This kind of tree building problem is generally solved by recursion, and this problem is no exception, dividing the left and right subtrees, and recursive construction.

This actually uses the well-known divide and conquer method Divide and Conquer, and similar problems are the same as the previous Different Ways to Add Parentheses method, using recursion to solve, dividing the left and right sub-arrays, recursive construction.

At the beginning, consider the interval [1, n] as a whole, and then you need to treat each number as the root node, which divides the left and right sub-intervals, and then call the recursive function separately, you will get two Node array, the next thing to do is to take one node each time from these two arrays, as the left and right child nodes of the current root node, and then add the root node to the result array.

Pitfalls

When start>end, if you directly return an empty list, size=0, then inserting the left and right subtrees will not work, i=0, i<left.size() loop will not enter So I use if-else to determine whether the list is empty So you must add a null to the list, let size=1
To create a root node, it must be in two for loops, because each time is an independent tree. I created the root node first, and then went into the for loop, but the result was repeated, because each for was operated on the same tree, and the added tree was changed.

I thought of the idea of creating left and right subtrees, but I didn’t figure out how to implement it and how to return the built subtrees to the upper level. This generate(start, end) is great.

Code

import java.util.ArrayList;
import java.util.List;

public class Unique_Binary_Search_Trees_II {

    public static void main(String[] args) {
        Unique_Binary_Search_Trees_II out = new Unique_Binary_Search_Trees_II();
        Solution s = out.new Solution();

        for (TreeNode each: s.generateTrees(3)) {
            System.out.println(each);
        }
    }

	/**
	 * Definition for a binary tree node.
	 * public class TreeNode {
	 *     int val;
	 *     TreeNode left;
	 *     TreeNode right;
	 *     TreeNode(int x) { val = x; }
	 * }
	 */

    // optimized
    public class Solution {

        public List<TreeNode> generateTrees(int n) {
            if (n == 0) {
                return new ArrayList<TreeNode>();
            }

            return generate(1, n);
        }

        public ArrayList<TreeNode> generate(int start, int end) {

            ArrayList<TreeNode> result = new ArrayList<TreeNode>();

            if (start > end) {
                result.add(null); // @note:@memorize:这里就是空的左树或者右树，是关键
                return result;
            }

            for (int i = start; i <= end; i++) {

                // i as root
                ArrayList<TreeNode> left = generate(start, i - 1);
                ArrayList<TreeNode> right = generate(i + 1, end);

                // append left subtree and right subtree
                // @note@note: should put inside for looping!, or, reference is modified onstantly!
                for (TreeNode l : left) {
                    for (TreeNode r : right) {

                        // 每次都要复制一个
                        TreeNode currentRoot = new TreeNode(i); // 当前的i作为head node

                        currentRoot.left = l;
                        currentRoot.right = r;

                        result.add(currentRoot);
                    }
                }
            }

            return result;
        }

    }

    // DP version
    public class Solution_iterative {

        public List<TreeNode> generateTrees(int n) {

            if (n == 0) {
                return new ArrayList<TreeNode>();
            }

            @SuppressWarnings("unchecked")
            List<TreeNode>[] result = new ArrayList[n + 1]; // @note: just like: new int[10]

            result[0] = new ArrayList<TreeNode>(); // empty tree
            result[0].add(null);

            for (int i = 1; i <= n; i++) {
                result[i] = new ArrayList<TreeNode>(); // store all combinations when n is i

                for (int leftIndex = 0; leftIndex < i; leftIndex++) {
                    for (TreeNode leftSub : result[leftIndex]) { // get ONE left subtree
                        for (TreeNode rightSub : result[i - leftIndex - 1]) { // get One right subtree
                            TreeNode tmpRoot = new TreeNode(leftIndex + 1);
                            tmpRoot.left = leftSub;

                            // @note:@memorize: key is here. should generate right subtree, where the start number is "1 + leftIndex"
                            tmpRoot.right = clone(rightSub, leftIndex + 1);
                            result[i].add(tmpRoot);
                        }
                    }
                }
            }
            return result[n];
        }

        // apply offset is still a local recursion
        private TreeNode clone(TreeNode n, int offset) { // name is nice, self-explanatory

            if (n == null) return null;
            TreeNode node = new TreeNode(n.val + offset);
            node.left = clone(n.left, offset);
            node.right = clone(n.right, offset);
            return node;
        }

    }
}

############

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<TreeNode> generateTrees(int n) {
        return generateTrees(1, n);
    }

    private List<TreeNode> generateTrees(int left, int right) {
        List<TreeNode> ans = new ArrayList<>();
        if (left > right) {
            ans.add(null);
        } else {
            for (int i = left; i <= right; ++i) {
                List<TreeNode> leftTrees = generateTrees(left, i - 1);
                List<TreeNode> rightTrees = generateTrees(i + 1, right);
                for (TreeNode l : leftTrees) {
                    for (TreeNode r : rightTrees) {
                        TreeNode node = new TreeNode(i, l, r);
                        ans.add(node);
                    }
                }
            }
        }
        return ans;
    }
}

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        def gen(left, right):
            ans = []
            if left > right: # this check instead of if left==right then return Node(left), less hassle
                ans.append(None)
            else:
                for i in range(left, right + 1):
                    left_trees = gen(left, i - 1)
                    right_trees = gen(i + 1, right)
                    for l in left_trees:
                        for r in right_trees:
                            node = TreeNode(i, l, r)
                            ans.append(node)
            return ans

        return gen(1, n)

############

class Solution(object):
  def generateTrees(self, n):
    """
    :type n: int
    :rtype: List[TreeNode]
    """

    def clone(root, offset):
      if root:
        newRoot = TreeNode(root.val + offset)
        left = clone(root.left, offset)
        right = clone(root.right, offset)
        newRoot.left = left
        newRoot.right = right
        return newRoot

    if not n:
      return []
    dp = [[]] * (n + 1)
    dp[0] = [None]
    for i in range(1, n + 1):
      dp[i] = []
      for j in range(1, i + 1):
        for left in dp[j - 1]:
          for right in dp[i - j]:
            root = TreeNode(j)
            root.left = left
            root.right = clone(right, j)
            dp[i].append(root)
    return dp[-1]

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        return gen(1, n);
    }

    vector<TreeNode*> gen(int left, int right) {
        vector<TreeNode*> ans;
        if (left > right) {
            ans.push_back(nullptr);
        } else {
            for (int i = left; i <= right; ++i) {
                auto leftTrees = gen(left, i - 1);
                auto rightTrees = gen(i + 1, right);
                for (auto& l : leftTrees) {
                    for (auto& r : rightTrees) {
                        TreeNode* node = new TreeNode(i, l, r);
                        ans.push_back(node);
                    }
                }
            }
        }
        return ans;
    }
};

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func generateTrees(n int) []*TreeNode {
	var gen func(left, right int) []*TreeNode
	gen = func(left, right int) []*TreeNode {
		var ans []*TreeNode
		if left > right {
			ans = append(ans, nil)
		} else {
			for i := left; i <= right; i++ {
				leftTrees := gen(left, i-1)
				rightTrees := gen(i+1, right)
				for _, l := range leftTrees {
					for _, r := range rightTrees {
						node := &TreeNode{i, l, r}
						ans = append(ans, node)
					}
				}
			}
		}
		return ans
	}

	return gen(1, n)
}

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function generateTrees(n: number): Array<TreeNode | null> {
    if (n == 0) return [];
    return helper(1, n);
}

function helper(start: number, end: number): Array<TreeNode | null> {
    let ans = [];
    if (start > end) {
        ans.push(null);
        return ans;
    }
    for (let i = start; i <= end; i++) {
        let lefts = helper(start, i - 1);
        let rights = helper(i + 1, end);
        for (let left of lefts) {
            for (let right of rights) {
                let root = new TreeNode(i, left, right);
                ans.push(root);
            }
        }
    }
    return ans;
}

95 - Unique Binary Search Trees II

Question

Algorithm

Pitfalls

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Pitfalls

Code

All Problems

All Solutions