leetcode题解-95-不同的二叉搜索树2

发表于 | 更新于 | 分类于

题目

官方解

简要改自官网解。

利用树的遍历，以递归方式实现不同二叉树的构造。

我们从序列 \(1 ...n\) 中取出数字 \(i\)，作为当前树的树根。于是，剩余 \(i - 1\) 个元素可用于左子树，\(n - i\) 个元素用于右子树。 如 前文所述，这样会产生 \(G(i - 1)\) 种左子树 和 \(G(n - i)\) 种右子树，其中 \(G\) 是卡特兰数。

现在，我们对序列 \(1 ... i - 1\) 重复上述过程，以构建所有的左子树；然后对 \(i + 1 ... n\) 重复，以构建所有的右子树。

这样，我们就有了树根 \(i\) 和可能的左子树、右子树的列表。

最后一步，对两个列表循环，将左子树和右子树连接在根上。

C++实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * 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:
    // [start, end]
    vector<TreeNode*> generate_trees(int start, int end)
    {
        vector<TreeNode*> all_trees;

        if (start > end)
        {
            all_trees.push_back(NULL);
            return all_trees;
        }

        // pick up a root 
        for (int i = 0; i <= end; ++i)
        {
            vector<TreeNode*> leftTrees = generate_trees(start, i - 1);
            vector<TreeNode*> rightTrees = generate_trees(i + 1, end);

            for (auto l : leftTrees)
            {
                for (auto r : rightTrees)
                {
                    TreeNode* curTree(i);
                    curTree->left = l;
                    curTree->right = r;
                    all_trees.push_back(curTree);
                }
            }

        }

        return all_trees;
    }

    vector<TreeNode*> generateTrees(int n) 
    {
        if (n == 0)
        {
            return vector<TreeNode*>();
        }
        else
        {
            return generate_trees(1, n);
        }
    }
};

Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
  public LinkedList<TreeNode> generate_trees(int start, int end) {
    LinkedList<TreeNode> all_trees = new LinkedList<TreeNode>();
    if (start > end) {
      all_trees.add(null);
      return all_trees;
    }

    // pick up a root
    for (int i = start; i <= end; i++) {
      // all possible left subtrees if i is choosen to be a root
      LinkedList<TreeNode> left_trees = generate_trees(start, i - 1);

      // all possible right subtrees if i is choosen to be a root
      LinkedList<TreeNode> right_trees = generate_trees(i + 1, end);

      // connect left and right trees to the root i
      for (TreeNode l : left_trees) {
        for (TreeNode r : right_trees) {
          TreeNode current_tree = new TreeNode(i);
          current_tree.left = l;
          current_tree.right = r;
          all_trees.add(current_tree);
        }
      }
    }
    return all_trees;
  }

  public List<TreeNode> generateTrees(int n) {
    if (n == 0) {
      return new LinkedList<TreeNode>();

Reference

官方解