Question

95. Unique Binary Search Trees II

中文文档

Description

Given an integer n, return _all the structurally unique BST's (binary search trees), which has exactly _n_ nodes of unique values from_ 1 _to_ n. Return the answer in any order.

 

Example 1:

Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

Example 2:

Input: n = 1
Output: [[1]]

 

Constraints:

• 1 <= n <= 8

Solutions

Solution 1: DFS (Depth-First Search)

We design a function $dfs(i, j)$ that returns all feasible binary search trees composed of $[i, j]$, so the answer is $dfs(1, n)$.

The execution steps of the function $dfs(i, j)$ are as follows:

1. If $i > j$, it means that there are no numbers to form a binary search tree at this time, so return a list consisting of a null node.
2. If $i \leq j$, we enumerate the numbers $v$ in $[i, j]$ as the root node. The left subtree of the root node $v$ is composed of $[i, v - 1]$, and the right subtree is composed of $[v + 1, j]$. Finally, we take the Cartesian product of all combinations of the left and right subtrees, i.e., $left \times right$, add the root node $v$, and get all binary search trees with $v$ as the root node.

The time complexity is $O(n \times G(n))$, and the space complexity is $O(n \times G(n))$. Where $G(n)$ is the Catalan number.

# Definition for a binary tree node.
# class TreeNode:
#   def __init__(self, val=0, left=None, right=None):
#     self.val = val
#     self.left = left
#     self.right = right
class Solution:
  def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
    def dfs(i: int, j: int) -> List[Optional[TreeNode]]:
      if i > j:
        return [None]
      ans = []
      for v in range(i, j + 1):
        left = dfs(i, v - 1)
        right = dfs(v + 1, j)
        for l in left:
          for r in right:
            ans.append(TreeNode(v, l, r))
      return ans

    return dfs(1, n)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *   int val;
 *   TreeNode left;
 *   TreeNode right;
 *   TreeNode() {}
 *   TreeNode(int val) { this.val = val; }
 *   TreeNode(int val, TreeNode left, TreeNode right) {
 *     this.val = val;
 *     this.left = left;
 *     this.right = right;
 *   }
 * }
 */
class Solution {
  public List<TreeNode> generateTrees(int n) {
    return dfs(1, n);
  }

  private List<TreeNode> dfs(int i, int j) {
    List<TreeNode> ans = new ArrayList<>();
    if (i > j) {
      ans.add(null);
      return ans;
    }
    for (int v = i; v <= j; ++v) {
      var left = dfs(i, v - 1);
      var right = dfs(v + 1, j);
      for (var l : left) {
        for (var r : right) {
          ans.add(new TreeNode(v, l, r));
        }
      }
    }
    return ans;
  }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *   int val;
 *   TreeNode *left;
 *   TreeNode *right;
 *   TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *   TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *   TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
  vector<TreeNode*> generateTrees(int n) {
    function<vector<TreeNode*>(int, int)> dfs = [&](int i, int j) {
      if (i > j) {
        return vector<TreeNode*>{nullptr};
      }
      vector<TreeNode*> ans;
      for (int v = i; v <= j; ++v) {
        auto left = dfs(i, v - 1);
        auto right = dfs(v + 1, j);
        for (auto l : left) {
          for (auto r : right) {
            ans.push_back(new TreeNode(v, l, r));
          }
        }
      }
      return ans;
    };
    return dfs(1, n);
  }
};

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */
func generateTrees(n int) []*TreeNode {
  var dfs func(int, int) []*TreeNode
  dfs = func(i, j int) []*TreeNode {
    if i > j {
      return []*TreeNode{nil}
    }
    ans := []*TreeNode{}
    for v := i; v <= j; v++ {
      left := dfs(i, v-1)
      right := dfs(v+1, j)
      for _, l := range left {
        for _, r := range right {
          ans = append(ans, &TreeNode{v, l, r})
        }
      }
    }
    return ans
  }
  return dfs(1, n)
}

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *   val: number
 *   left: TreeNode | null
 *   right: TreeNode | null
 *   constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 *   }
 * }
 */

function generateTrees(n: number): Array<TreeNode | null> {
  const dfs = (i: number, j: number): Array<TreeNode | null> => {
    if (i > j) {
      return [null];
    }
    const ans: Array<TreeNode | null> = [];
    for (let v = i; v <= j; ++v) {
      const left = dfs(i, v - 1);
      const right = dfs(v + 1, j);
      for (const l of left) {
        for (const r of right) {
          ans.push(new TreeNode(v, l, r));
        }
      }
    }
    return ans;
  };
  return dfs(1, n);
}

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//   TreeNode {
//     val,
//     left: None,
//     right: None
//   }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn generate_trees(n: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
    Self::dfs(1, n)
  }

  fn dfs(i: i32, j: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
    let mut ans = Vec::new();
    if i > j {
      ans.push(None);
      return ans;
    }
    for v in i..=j {
      let left = Self::dfs(i, v - 1);
      let right = Self::dfs(v + 1, j);
      for l in &left {
        for r in &right {
          ans.push(
            Some(
              Rc::new(
                RefCell::new(TreeNode {
                  val: v,
                  left: l.clone(),
                  right: r.clone(),
                })
              )
            )
          );
        }
      }
    }
    ans
  }
}