95. Unique Binary Search Trees II (Medium)

https://leetcode.com/problems/unique-binary-search-trees-ii/

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

Solutions

class Solution {

    // The straight forward solution is firstly sort out all the possible tree patterns. Then for each tree,
    // populate the values by inorder traversal.

    int val = 1;

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

        // First get all the patterns of trees
        List<TreeNode> ans = recurse(n);

        for (TreeNode node : ans) {
            // every time reset the val count
            val = 1;

            // Inorder traversal and set the values
            setValue(node);
        }

        return ans;
    }

    private void setValue(TreeNode root) {
        if (root == null) {
            return;
        }

        setValue(root.left);

        root.val = val++;

        setValue(root.right);
    }

    private List<TreeNode> recurse(int n) {
        if (n == 0) {
            return null;
        }

        List<TreeNode> ans = new ArrayList<>();

        if (n == 1) {
            ans.add(new TreeNode(0));

            return ans;
        }

        for (int i = 0; i < n; i++) {
            // left i nodes
            List<TreeNode> left = recurse(i);

            // right n - i - 2 nodes
            List<TreeNode> right = recurse(n - i - 1);

            // combine the left and right branch
            combine(left, right, ans);
        }

        return ans;
    }

    private void combine(List<TreeNode> left, List<TreeNode> right, List<TreeNode> ans) {
        // Technically, below situation will never happen
        if (left == null && right == null) {
            return;
        }

        // if left == null
        if (left == null) {
            for (TreeNode node : right) {
                TreeNode root = new TreeNode(0);

                root.left = null;
                root.right = node;

                ans.add(root);
            }

            return;
        }

        // if right == null
        if (right == null) {
            for (TreeNode node : left) {
                TreeNode root = new TreeNode(0);

                root.left = node;
                root.right = null;

                ans.add(root);
            }

            return;
        }

        // if left != null && right != null
        for (TreeNode l : left) {
            for (TreeNode r : right) {
                TreeNode root = new TreeNode(0);

                root.left = l;
                root.right = r;

                ans.add(root);
            }
        }
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:18

results matching ""

    No results matching ""