首页 > 其他 > 详细

Unique Binary Search Trees II

时间:2015-03-15 21:01:03      阅读:201      评论:0      收藏:0      [点我收藏+]

Unique Binary Search Trees II

问题:

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

思路:

  dfs

我的代码:

技术分享
public class Solution {
    public List<TreeNode> generateTrees(int n) {
        int[] num = new int[n];
        for(int i = 0; i < n; i++)
        {
            num[i] = i + 1;
        }
        return findNode(num, 0, n);
    }
    public List<TreeNode> findNode(int[] num, int start, int end)
    {
        if(start == end)
        {
            List<TreeNode> list = new ArrayList<TreeNode>();
            list.add(null);
            return list;
        }
        if(start + 1 == end) 
        {
            List<TreeNode> list = new ArrayList<TreeNode>();
            list.add(new TreeNode(num[start]));
            return list;
        }
        List<TreeNode> rst = new ArrayList<TreeNode>();
        for(int i = start; i < end; i++)
        {
           
            List<TreeNode> left = findNode(num, start, i);
            List<TreeNode> right = findNode(num, i + 1, end);
            for(TreeNode l: left)
            {
                for(TreeNode r: right)
                {
                    TreeNode root = new TreeNode(num[i]);
                    root.left = l;
                    root.right = r;
                    rst.add(root);
                }
            }
        }
        return rst;
    }
}
View Code

学习之处:

  • 需要每一次重新 新建一个TreeNode root = new TreeNode(num[i])因为是地址啊,地址啊!这一点一定要注意。

Unique Binary Search Trees II

原文:http://www.cnblogs.com/sunshisonghit/p/4340239.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!