LeetCode 95 - Unique Binary Search Trees II

题干

给定一个数字 n ，返回可由 1 ~ n 构成的所有二叉搜索树。

思路

还是插入顺序的问题。但是为什么结果不是 $n!$ 颗树呢？
假设 i ， j 先后插入树。如果完全按照顺序来，那 j 必定是 i 的孩子。而在向下遍历找插入点时，如果 i 在左子树，而 j 要去右子树，那 j 必然就不能成为 i 的孩子，所以就会造成一些重复。

这个条件应该怎么判断？
假设当前节点是 curr ，那 i 和 j 不在 curr 的同边的情况是 i < curr < j 或 j < curr < i 。
概括一下就是 (i - curr) * (j - curr) < 0 。

思路就是这样：

设当前要插入 i 。
for 树 in 上一步生成的树：
    for k in (1, i - 1):
        判断能否在 k 后插入 i
        if 能插入：
            克隆原树，插入 i
            加入 list
    加入 i 作为根节点的树

这个时间空间就不算了。。

代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> res = new ArrayList<>();
        if (n == 0) {
            return res;
        }
        TreeNode tree = new TreeNode(1);
        res.add(tree);
        for (int i = 2; i <= n; i++) {
            // 获取上一步生成的树的数量
            int lastSize = res.size();
            for(int j = 0; j < lastSize; j++) { 
                // 由于每次在后面加，然后会移除第一个，所以每次第一个都是新的
                TreeNode currTree = res.get(0);
                TreeNode newTree = null;
                for (int k = 1; k < i; k++) {
                    // 如果上一轮生成了新树，那就再深复制一个
                    if (newTree == null) {
                        newTree = clone(currTree);                   
                    }
                    // 如果可以插入 i 作为 k 的子节点
                    if (insertAfter(i, k, newTree)) {
                        res.add(newTree);
                        newTree = null;
                    }
                }
                // 以 i 作为根的树
                newTree = new TreeNode(i);
                newTree.left = currTree;
                res.add(newTree);
                res.remove(0);
            }
        }
        return res;
    }
    public boolean insertAfter(int item, int key, TreeNode tree) {
        TreeNode curr = tree;
        while (curr.val != key) {
            if ((item - curr.val) * (key - curr.val) < 0) {
                return false;
            }
            if (key < curr.val) {
                curr = curr.left;
            } else {
                curr = curr.right;
            }
        }
        TreeNode tmp = new TreeNode(item);
        if (curr.right != null) {
            tmp.left = curr.right;
        }
        curr.right = tmp;
        return true;
    }
    public TreeNode clone(TreeNode tree) {
        TreeNode copy = new TreeNode(tree.val);
        clone(tree, copy);
        return copy;
    }
    public void clone(TreeNode tree, TreeNode copy) {
        if (tree == null) {
            return;
        }
        if (tree.left != null) {
            copy.left = new TreeNode(tree.left.val);
            clone(tree.left, copy.left);
        }
        if (tree.right != null) {
            copy.right = new TreeNode(tree.right.val);
            clone(tree.right, copy.right);
        }
    }
}

题干
思路

LeetCode 95 - Unique Binary Search Trees II

题干

思路

FEATURED TAGS

FRIENDS