Number of Ways to Reorder Array to Get Same BST LeetCode solution in C++

1
class Solution {
2
  struct Node {
3
    unique_ptr<Node> left;
4
    unique_ptr<Node> right;
5
    int val = 0;
6

7
    void insert(int x) {
8
      if (x < val) {
9
        if (left) {
10
          left->insert(x);
11
        } else {
12
          left = make_unique<Node>();
13
          left->val = x;
14
        }
15
      } else {
16
        if (right) {
17
          right->insert(x);
18
        } else {
19
          right = make_unique<Node>();
20
          right->val = x;
21
        }
22
      }
23
    }
24

25
    bool isLeaf() const {
26
      return !left && !right;
27
    }
28
  };
29

30
  constexpr static const int ModBase = 1'000'000'007;
31

32
  /// the number of ways to interleave two sequences of length x and y
33
  /// respectively. this feels like very similar to combinations C(x+y, x).
34
  static int interleaves(int x, int y) {
35
    static int memo[1001][1001] = {-123};
36
    if (memo[0][0] == -123) {
37
      // initialize the memo elements to non-zero,
38
      // because zero can be a valid value after the modulo op.
39
      memset(memo, -1, sizeof(memo));
40
    }
41
    // todo: or just compute this table bottom-up.
42
    if (x == 0 || y == 0) {
43
      return 1;
44
    }
45
    if (x > y) {
46
      swap(x, y);
47
    }
48
    if (memo[x][y] != memo[0][0]) {
49
      return memo[x][y];
50
    }
51
    return memo[x][y] = (interleaves(x - 1, y) + interleaves(x, y - 1)) % ModBase;
52
  }
53

54
  /// return a tuple which represents <CountOfNodes, Combinations>
55
  tuple<int, int> traverseNode(Node *node) {
56
    if (!node) {
57
      return {0, 0};
58
    }
59
    if (node->isLeaf()) {
60
      return {1, 1};
61
    }
62
    if (node->left) {
63
      auto [leftNodeCount, leftCombos] = traverseNode(node->left.get());
64
      if (node->right) {
65
        auto [rightNodeCount, rightCombos] = traverseNode(node->right.get());
66
        int totalCombos = ((int64_t)leftCombos * rightCombos) % ModBase;
67
        totalCombos = ((int64_t)totalCombos * interleaves(leftNodeCount, rightNodeCount)) % ModBase;
68
        return {1 + leftNodeCount + rightNodeCount, totalCombos};
69
      } else { // right side is empty
70
        return {1 + leftNodeCount, leftCombos};
71
      }
72
    } else { // left side is empty, but it must have the right side, because
73
             // it's not a leaf.
74
      auto [rightNodeCount, rightCombos] = traverseNode(node->right.get());
75
      return {1 + rightNodeCount, rightCombos};
76
    }
77
  }
78

79
 public:
80
  int numOfWays(vector<int> &nums) {
81
    // create the BST.
82
    auto root = make_unique<Node>();
83
    root->val = nums[0];
84
    for (int i = 1; i < nums.size(); ++i) {
85
      root->insert(nums[i]);
86
    }
87

88
    auto [nodeCount, combos] = traverseNode(root.get());
89
    return combos - 1;
90
  }
91
};