Menu

Subscribe

LeetCode 95 [Unique Binary Search Trees II]

ShuyuFang on Leetcode

题目链接

题目描述

  • 给定一个整数，要求返回所有由值为1-n的结点组成的二叉排序树。

解题思路

  1. 首先需要考虑n的取值，若取值不大于0，则不会形成任何二叉树。
  2. 对于n>0的情况，可以用分治的思想来处理，每个结点轮流作为根结点，那么它的左子树就是由所有比该结点的值小的其他结点构成的，它的右子树就是由所有比该结点大的值构成的。
  3. 对于左子树与右子树，又可以轮流以某个结点作为根结点，一直到无法再分为止。
  4. 由于左子树可能有a种形式，右子树也可能有b种形式，所以以某个结点为根的树的集合其实需要对左右子树的情况进行一一匹配，最终可以得出a*b种形式。
  5. 需要特别注意一种情况，子树为空或者仅有一个结点，这两种情况实质都包含了一种形式，需要同等考虑。
  6. 每次以某个结点为根进行计算，平均时间复杂度为O(log n)，对n个结点进行计算，时间复杂度即为O(n * log n)。

C++代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        vector<TreeNode*> result;
        if (n < 1) {
            return result;
        }
        return generateTreesOfRange(1, n);
    }
    vector<TreeNode*> generateTreesOfRange(int beg, int end) {
        vector<TreeNode*> result;
        if (beg > end) {
            result.push_back(NULL);
            return result;
        }
        for (int i = beg; i <= end; ++i) {
            vector<TreeNode*> leftTrees = generateTreesOfRange(beg, i - 1);
            vector<TreeNode*> rightTrees = generateTreesOfRange(i + 1, end);
            for (int j = 0; j < leftTrees.size(); ++j) {
                for (int k = 0; k < rightTrees.size(); ++k) {
                    TreeNode* root = new TreeNode(i);
                    root->left = leftTrees[j];
                    root->right = rightTrees[k];
                    result.push_back(root);
                }
            }
        }
        return result;
    }
};