leetcode習題集——95. 不同的二叉搜尋樹 II

題目

給定一個整數 n，生成所有由 1 … n 為節點所組成的二叉搜尋樹。

示例:

輸入: 3

輸出:

[

[1,null,3,2],

[3,2,null,1],

[3,1,null,null,2],

[2,1,3],

[1,null,2,null,3]

]

解釋:

以上的輸出對應以下 5 種不同結構的二叉搜尋樹：

算法

public class P95 {

    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> rList = new ArrayList<>();
        if(n<1){
            return rList;
        }
        for(int i = 1;i<=n;i++){
            if(i==1){
                rList.add(new TreeNode(1));
            }else {
                List<TreeNode> tmp = new ArrayList<>();
                tmp.addAll(rList);
                rList.clear();
                for(TreeNode root : tmp){
                    //直接插在原樹頭部
                    TreeNode newTree1 = copyTrees(root);
                    TreeNode newroot = new TreeNode(i);
                    newroot.left = newTree1;
                    rList.add(newroot);
                    //循環插入原樹的右子樹上
                    TreeNode p = root;
                    while(p!=null){
                        TreeNode newTree2 = copyTrees(root);
                        TreeNode q = newTree2;
                        while(q.val!=p.val){
                            q = q.right;
                        }
                        TreeNode newi = new TreeNode(i);
                        newi.left = q.right;
                        q.right = newi;
                        rList.add(newTree2);
                        p = p.right;
                    }
                }
            }
        }
        return rList;
    }
    private TreeNode copyTrees(TreeNode root1){
        if(root1==null){
            return null;
        }
        TreeNode newNode = new TreeNode(root1.val);
        newNode.left = copyTrees(root1.left);
        newNode.right = copyTrees(root1.right);
        return newNode;
    }
}
           

思路(借鑒leetcode評論思路)：

1. 從小往大生成，新來一數，肯定比現有的節點都大 那麼n可以成為現在所有樹的父節點，并且他們都是n的左子樹 第二步就是沿着現有子樹的右側嘗試不斷插入。
2. 如果插入以後，n還有子樹，那麼這些子樹都是n的左子樹