[leetcode]95 Unique Binary Search Trees II (Medium)

字母题添加链接描述

一开始完全没有思路。。百度看了别人的思路，对于这种递归构造的题目还是不熟，得多做做了。

这个题目难在构造出来。一般构造树都需要递归。

从1–n中任意选择一个数当做根节点，所以其左边的数字构成其左子树，右边的数字当做右子树。

因为要求出所有的子树，所以当左子树固定的时候，把所有可能的右子树都构成，然后再变换左子树。

这个代码难理解的地方在于left_nodes 和 right_nodes的求法，这个一定要结合递归的终止条件去看，

当选择的根节点的值i比left小的时候，那么其实左子树就是空了。

如果把这个理解了，那么下面的对左右子树的遍历应该也不难理解。

class Solution {

 public:

  vector<TreeNode *> generateTrees(int n) {

    vector<TreeNode *> res;

    if (n <= 0) return res;

    return helper(1, n);

  }

 private:

  vector<TreeNode *> helper(int start, int end) {

    vector<TreeNode *> subTree;

    if (start > end) {

      subTree.push_back(NULL);

      return subTree;

    }

    for (int k = start; k <= end; k++) {

      vector<TreeNode *> leftSubs = helper(start, k - 1);

      vector<TreeNode *> rightSubs = helper(k + 1, end);

      for (int i = 0; i < leftSubs.size(); i++) {

        for (int j = 0; j < rightSubs.size(); j++) {

          TreeNode *node = new TreeNode(k);

          node->left = leftSubs[i];

          node->right = rightSubs[j];

          subTree.push_back(node);

        }

      }

    }

    return subTree;

  }

};

巴特西

[leetcode]95 Unique Binary Search Trees II (Medium)

最新文章

热门文章