美文网首页
Leetcode95

Leetcode95

作者: zhouwaiqiang | 来源:发表于2018-11-05 20:40 被阅读0次

    题目要求

    给定一个正整数n,求出它所产生的所有的二叉查找树(左边比根节点小,右边比根节点大),其数的组合由1-n

    实现过程(给出的solution方法,个人理解)

    • 由于是给定的一个连续的数组成的二叉查找树,那么应该具有以下的性质:左边始终比根节点小,右边始终比根节点大的特性,那么假设我们设置i为根节点,那么[1, i-1]只能在左子树,[i+1, n]只能在右子树,依次递归向上合并即可得到完整的二叉查找树,如下图中所示:

      image
    • 以上描述按照动态规划的概念解法如下:
    • 假设我们要求的是一个以i为根节点的所有的二叉查找树的集合,设为G(i)那么最优子结构应该是G(n) = εG(i)(i为1-n)
    • 根据左右子树的组合,可以得出状态转移方程为G(i) = G(1, i-1)(左半边子树) + G(i+1, n)(右半边子树),G(x,y)表示从x到y组成的二叉查找树
    • 同时边界条件为x<=y && x >= 1 && y >= 1

    代码复现

    public class Solution {
        public List<TreeNode> generateTree(int n) {
            if (n == 0) return new ArrayList<TreeNode>();
            return generate_tree(1, n);
        }
        
        private static List<TreeNode> generate_tree(int start, int end) {
            List<TreeNode> result = new ArrayList<>();
            if (start > end) return result.add(null);
            for (int i=start; i<=end; i++) {
                List<TreeNode> left_trees = genenrate_tree(start, i-1);
                List<TreeNode> right_trees = generate_tree(i+1, end);
                for (TreeNode l : left_trees) {
                    for (TreeNode r : right_trees) {
                        TreeNode current_node = new TreeNode(i);
                        current_node.left = l;
                        current_node.right = r;
                        result.add(current_node);
                    }
                }
            }
            return result;
        }
    }
    

    个人博客链接

    http://www.waiqiang.ren/

    相关文章

      网友评论

          本文标题:Leetcode95

          本文链接:https://www.haomeiwen.com/subject/oljexqtx.html