首页 > 试题广场 >

不同的二叉搜索树 ii

[编程题]不同的二叉搜索树 ii
  • 热度指数:10152 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
给定一个值n,请生成所有的存储值1...n.的二叉搜索树BST)的结构
例如:
给定n=3,你的程序应该给出下面五种不同的二叉搜索树(BST)

示例1

输入

3

输出

[{1,#,2,#,3},{1,#,3,2},{2,1,3},{3,1,#,#,2},{3,2,#,1}]

说明:本题目包含复杂数据结构TreeNode,点此查看相关信息
//递归思路去解,逻辑就相当清楚了
public ArrayList<TreeNode> generateTrees (int n) {
            // write code here
         if(n==0) {
                 ArrayList<TreeNode> res=new ArrayList<TreeNode>();
                 res.add(null);
                 return res;
         }
         if(n==1) {
             ArrayList<TreeNode> res=new ArrayList<>();
             res.add(new TreeNode(1));
             return res;
         }
         return generate(1,n);
        }
     private TreeNode clone(TreeNode n) {
            if (n == null)
                return null;
            TreeNode node = new TreeNode(n.val);
            node.left = clone(n.left);
            node.right = clone(n.right);
            return node;
        }
     public ArrayList<TreeNode> generate(int start,int end) {
         ArrayList<TreeNode>  item=new ArrayList<>();
         if(end-start==0) {
             TreeNode data=new TreeNode(start);
             item.add(data); 
             return item;
         }else {
            for (int i = start; i <=end; i++) {
                if(i==start) {
                ArrayList<TreeNode> data=generate(i+1, end);
                for (int j = 0; j < data.size(); j++) {
                    TreeNode ele=new TreeNode(i);
                    ele.right=data.get(j);
                    item.add(ele);
                }
                }else if(i==end) {
                    ArrayList<TreeNode> data=generate(start, end-1);
                    for (int j = 0; j < data.size(); j++) {
                        TreeNode ele=new TreeNode(i);
                        ele.left=data.get(j);
                        item.add(ele);
                    }
                }else {
                    ArrayList<TreeNode> data1=generate(i+1, end);
                    ArrayList<TreeNode> data2=generate(start,i-1);
                    for (int j = 0; j < data2.size(); j++) {
                        for (int j2 = 0; j2 < data1.size(); j2++) {
                            TreeNode ele=new TreeNode(i);
                            ele.right=clone(data1.get(j2));
                            ele.left=clone(data2.get(j));
                            item.add(ele);
                        }
                    }
                }
            
         }
         return item;
     }
发表于 2021-02-15 22:42:54 回复(0)
import java.util.*;
public class Solution {
    public ArrayList<TreeNode> generateTrees(int n) {
		return createTree(1, n);
	}
	public ArrayList<TreeNode> createTree(int low, int high) {
		ArrayList<TreeNode> result = new ArrayList<>();
		if(low > high) {
			result.add(null);
			return result;
		}
		for (int i = low; i <= high; i ++) {
			// 求根结点i的左右子树集合
			ArrayList<TreeNode> left = createTree(low, i - 1);
			ArrayList<TreeNode> right = createTree(i + 1, high);
			for (int j = 0; j < left.size(); j ++) {
				for (int k = 0; k < right.size(); k ++) {
					// 将左右子树相互配对,每一个左子树都与所有右子树匹配,每一个右子树都与所有的左子树匹配
					TreeNode newNode = new TreeNode(i);
					newNode.left = left.get(j);
					newNode.right = right.get(k);
					result.add(newNode);
				}
			}
		}
		return result;
	}
}

编辑于 2017-03-25 18:39:35 回复(7)
public class Solution { public List<TreeNode> generateTrees(int n) { return genTrees(1,n);
    } public List<TreeNode> genTrees (int start, int end)
    { List<TreeNode> list = new ArrayList<TreeNode>(); if(start>end)
        { list.add(null); return list;
        } if(start == end){ list.add(new TreeNode(start)); return list;
        } List<TreeNode> left,right; for(int i=start;i<=end;i++)
        {
            
            left = genTrees(start, i-1);
            right = genTrees(i+1,end); for(TreeNode lnode: left)
            { for(TreeNode rnode: right)
                {
                    TreeNode root = new TreeNode(i);
                    root.left = lnode;
                    root.right = rnode; list.add(root);
                }
            }
                
        } return list;
    }
}


发表于 2017-03-12 11:15:12 回复(0)

问题信息

难度:
3条回答 14514浏览

热门推荐

通过挑战的用户

查看代码