Unique Binary Search Trees II

发布于 2025-02-22 13:01:31 字数 7606 浏览 0 评论 0 收藏 0

Source

leetcode: Unique Binary Search Trees II | LeetCode OJ
lintcode: (164) Unique Binary Search Trees II

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

Example
Given n = 3, your program should return all 5 unique BST's shown below.

   1     3   3    2    1
  \     /   /    / \    \
   3   2   1    1   3    2
  /   /     \         \
   2   1     2         3

题解

题 Unique Binary Search Trees 的升级版，这道题要求的不是二叉搜索树的数目，而是要构建这样的树。分析方法仍然是可以借鉴的，核心思想为利用『二叉搜索树』的定义，如果以 i 为根节点，那么其左子树由[1, i - 1]构成，右子树由[i + 1, n] 构成。要构建包含 1 到 n 的二叉搜索树，只需遍历 1 到 n 中的数作为根节点，以 i 为界将数列分为左右两部分，小于 i 的数作为左子树，大于 i 的数作为右子树，使用两重循环将左右子树所有可能的组合链接到以 i 为根节点的节点上。

容易看出，以上求解的思路非常适合用递归来处理，接下来便是设计递归的终止步、输入参数和返回结果了。由以上分析可以看出递归严重依赖数的区间和 i ，那要不要将 i 也作为输入参数的一部分呢？首先可以肯定的是必须使用『数的区间』这两个输入参数，又因为 i 是随着『数的区间』这两个参数的，故不应该将其加入到输入参数中。分析方便，不妨设『数的区间』两个输入参数分别为 start 和 end .

接下来谈谈终止步的确定，由于根据 i 拆分左右子树的过程中，递归调用的方法中入口参数会缩小，且存在 start <= i <= end , 故终止步为 start > end . 那要不要对 start == end 返回呢？保险起见可以先写上，后面根据情况再做删改。总结以上思路，简单的伪代码如下：

helper(start, end) {
  result;
  if (start > end) {
    result.push_back(NULL);
    return;
  } else if (start == end) {
    result.push_back(TreeNode(i));
    return;
  }

  // dfs 
  for (int i = start; i <= end; ++i) {
    leftTree = helper(start, i - 1);
    rightTree = helper(i + 1, end);
    // link left and right sub tree to the root i
    for (j in leftTree ){
      for (k in rightTree) {
        root = TreeNode(i);
        root->left = leftTree[j];
        root->right = rightTree[k];
        result.push_back(root);
      }
    }
  }

  return result;
}

大致的框架如上所示，我们来个简单的数据验证下，以[1, 2, 3]为例，调用堆栈图如下所示：

helper(1,3)
- [leftTree]: helper(1, 0) ==> return NULL
- ---loop i = 2---
- [rightTree]: helper(2, 3)
  1. [leftTree]: helper(2,1) ==> return NULL
  2. [rightTree]: helper(3,3) ==> return node(3)
  3. [for loop]: ==> return (2->3)
- ---loop i = 3---
  1. [leftTree]: helper(2,2) ==> return node(2)
  2. [rightTree]: helper(4,3) ==> return NULL
  3. [for loop]: ==> return (3->2)
...

简单验证后可以发现这种方法的 核心为递归地构造左右子树并将其链接到相应的根节点中。 对于 start 和 end 相等的情况的，其实不必单独考虑，因为 start == end 时其左右子树均返回空，故在 for 循环中返回根节点。当然单独考虑可减少递归栈的层数，但实际测下来后发现运行时间反而变长了不少 :(

Python

"""
Definition of TreeNode:
class TreeNode:
  def __init__(self, val):
    this.val = val
    this.left, this.right = None, None
"""
class Solution:
  # @paramn n: An integer
  # @return: A list of root
  def generateTrees(self, n):
    return self.helper(1, n)

  def helper(self, start, end):
    result = []
    if start > end:
      result.append(None)
      return result

    for i in xrange(start, end + 1):
      # generate left and right sub tree
      leftTree = self.helper(start, i - 1)
      rightTree = self.helper(i + 1, end)
      # link left and right sub tree to root(i)
      for j in xrange(len(leftTree)):
        for k in xrange(len(rightTree)):
          root = TreeNode(i)
          root.left = leftTree[j]
          root.right = rightTree[k]
          result.append(root)

    return result

C++

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *   int val;
 *   TreeNode *left, *right;
 *   TreeNode(int val) {
 *     this->val = val;
 *     this->left = this->right = NULL;
 *   }
 * }
 */
class Solution {
public:
  /**
   * @paramn n: An integer
   * @return: A list of root
   */
  vector<TreeNode *> generateTrees(int n) {
    return helper(1, n);
  }

private:
  vector<TreeNode *> helper(int start, int end) {
    vector<TreeNode *> result;
    if (start > end) {
      result.push_back(NULL);
      return result;
    }

    for (int i = start; i <= end; ++i) {
      // generate left and right sub tree
      vector<TreeNode *> leftTree = helper(start, i - 1);
      vector<TreeNode *> rightTree = helper(i + 1, end);
      // link left and right sub tree to root(i)
      for (int j = 0; j < leftTree.size(); ++j) {
        for (int k = 0; k < rightTree.size(); ++k) {
          TreeNode *root = new TreeNode(i);
          root->left = leftTree[j];
          root->right = rightTree[k];
          result.push_back(root);
        }
      }
    }

    return result;
  }
};

Java

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *   public int val;
 *   public TreeNode left, right;
 *   public TreeNode(int val) {
 *     this.val = val;
 *     this.left = this.right = null;
 *   }
 * }
 */
public class Solution {
  /**
   * @paramn n: An integer
   * @return: A list of root
   */
  public List<TreeNode> generateTrees(int n) {
    return helper(1, n);
  }

  private List<TreeNode> helper(int start, int end) {
    List<TreeNode> result = new ArrayList<TreeNode>();
    if (start > end) {
      result.add(null);
      return result;
    }

    for (int i = start; i <= end; i++) {
      // generate left and right sub tree
      List<TreeNode> leftTree = helper(start, i - 1);
      List<TreeNode> rightTree = helper(i + 1, end);
      // link left and right sub tree to root(i)
      for (TreeNode lnode: leftTree) {
        for (TreeNode rnode: rightTree) {
          TreeNode root = new TreeNode(i);
          root.left = lnode;
          root.right = rnode;
          result.add(root);
        }
      }
    }

    return result;
  }
}