lcBinarySearchTreeAndRecursiveWay

Posted on Edited on

0 递归和bst

1 构建bst 0108. 将有序数组转换为二叉搜索树

1 题目

https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/

2 解题思路

  • 1 AVL tree最主要的特性在于，任何子树的左子树和右子树的高度差不超过1，所以方法为：
    • 1.1 每次找到数组中间的值作为root，然后两边分别作为左右子树，左边都比root小，右边都大，刚好满足AVL要求
      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
      /**
       * 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:
          TreeNode* sortedArrayToBST(vector<int>& nums) {
              // find root whose left size and right size shall equal
              int n = nums.size();
              if(n <= 0) {
                  return nullptr;
              }
              vector<int> left(nums.begin(), nums.begin() + n / 2);
              vector<int> right(nums.begin() + n / 2 + 1, nums.end());
              TreeNode* root = new TreeNode(
                  nums[n/2]
                  sortedArrayToBST(left),
                  sortedArrayToBST(right)
              );
              return root;
          }
      };

2 select k from n: C(n, k)

1
2
3
4
5
6
7
8
9
10
11
void selectKFromN(int st, int k, vector<vector<int>>& res, vector<int>& nums, vector<int>& tmpRes) {
    if(k == 0) {
        res.emplace_back(tmpRes);
        return;
    }
    for(int i = st; i < nums.size() - k + 1; ++i) {
        tmpRes.emplace_back(nums[i]);
        selectKFromN(i + 1, k - 1, res, nums, tmpRes);
        tmpRes.pop_back();
    }
}

1 递归

0025 最大因数联通分量大小

1 题目

https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

2 解题思路

  • 1 个人思路：
    • 首先很明显能够发现子问题的痕迹，子问题就是翻转长度为k的链表
    • 翻转用长度为k的栈去模拟即可
  • 2 优化： 使用常数空间：
    • 使用三个指针，a->b->c的链表的话，那么就是说(三个指针相当于滑动窗口的感觉)：
    • 记录下a,b,c的指针，然后把a<-b<-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
/** 
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        // return headK -> reverse(afterHeadK, k);
        return reverse(head, k);
    }

    ListNode* reverse(ListNode* head, int k ) {
        ListNode* tmp = head;
        vector<ListNode*> vec = {};
        for(int i = 0; i < k; ++i) {
            if(tmp != nullptr) {
                vec.emplace_back(tmp);
                tmp = tmp -> next;
            }
        }

        if(vec.size() != k) {
            return head;
        }

        ListNode* nextHead = vec.back()->next;

        for(int i = k-1; i >= 1; --i) {
            // cout << i << "**" << endl;
            vec[i]->next = vec[i-1];
            // cout << vec[i]->val << " -> " << vec[i-1]->val << endl;
        }
        vec[0]->next = reverse(nextHead, k);
        
        // cout << "asdf**" << endl;
        return vec.back();
    }
};

1.1

0761 makeLargestSpecial 特殊的二进制序列

1 题目

https://leetcode-cn.com/problems/special-binary-string

2 解题思路

  • 1 个人思路：
    • 首先这个特殊子序列，采用合理的括号串去理解特殊子序列就好了
    • 然后大致的递归思路：
      • 1.1 首先找到原来串里所有特殊的子序列
      • 1.2 将这些子序列按照字典序排序
      • 1.3 排序后加起来得到结果
      • 1.4 eg： 10 1100 111000，这个串可以分成三个特殊子序列：那么最大字典序显然就是 111000 1100 10
    • 上面的还有其他问题，若子串一开始不能分为特殊子序列呢？
      • eg：1 10 1100 0， 那么首先剥去外壳，然后再递归进去，对10 1100采用上述子序列方法
    • 递归返回？当子序列长度小于等于2，就直接返回字符串北盛即可
    • 有个很容易出错误的示例需要注意：

      we shall reArrange first and then sort,
      because when we reArrage, we my produce bigger subStr,
      if we sort first and reArrange all subpart we could get false res: eg:
      input: “11100011010101100100”
      false Result: “111000 11100101010100” // part2 is bigger subStr, so we shall reArrange all sub first and then sort
      std result: “11100101010100 111000” 

      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
      57
      58
      59
      60
      61
      62
      63
      64
      65
      class Solution {
      public:
          string makeLargestSpecial(string s) {
              string res = reArrange(s);
              // string lastRes = "";
              // while(res != reArrange(res)){
              //     res = reArrange(res);
              // };
              return res;
          }

          string reArrange(string s) {
              // cout << "c1->"  << s << endl;
              int n = s.size();
              if(s.size() <= 2) {
                  // cout << "less than 2: " << s << endl;
                  return s;
              }

              // firstly, get all special subStr and sort as the lexical order
              vector<string> subStr;

              int st = 0;
              int cntRedundantNumberOne = 1;
              for(int i = st + 1; i < n; ++i) {
                  cntRedundantNumberOne += (s[i] == '1' ? 1 : -1);
                  if(0 == cntRedundantNumberOne) {
                      subStr.emplace_back(s.substr(st, i - st + 1));
                      st = i + 1;
                      cntRedundantNumberOne = 0;
                  }
              }

              if(1 == subStr.size()) {

                  return s.substr(0, 1) + reArrange(s.substr(1, n-2)) + s.substr(n-2, 1);
              }

              // for(auto i : subStr) {
              //     cout << i << endl;
              // }
              
              
              // secondly, sort all sub part and sum up
              // cout << "a" << endl;
              for(int i = 0; i < subStr.size(); ++i) {
                  subStr[i] = reArrange(subStr[i]);
              }
              // we shall reArrange first and then sort,
              // because when we reArrage, we my produce bigger subStr, 
              // if we sort first and reArrange all subpart we could get false res: eg: 
              // input:        "11100011010101100100"
              // false Result: "111000 11100101010100" // part2 is bigger subStr, so we shall reArrange all sub first and then sort
              // std result:   "11100101010100 111000" 
              sort(subStr.begin(), subStr.end(), std::greater<string>());

              string res = "";
              for(auto s : subStr) {
                  res += s;
              }

              // cout << "c2" << endl;
              return res;
          }
      };

0010 isMatch 正则表达式匹配

1 题目

https://leetcode-cn.com/problems/regular-expression-matching

2 解题思路

  • 0 心得：
    • 递归适用于减小规模后问题的处理方式不会发生改变的场景
    • 对于递归，得明白当层递归处理会如何将问题规模减小
  • 1 个人思路：
    • 首先这个字符串匹配，需要理解每一次能够用p去匹配什么？然后怎么匹配
    • 1.1 首先每次递归，p的规模减小肯定是在p的头部： 对于p的匹配类型，有3种：
      • 1.1.1 s = ab, p = ab, 那么就用p的第一个字母去匹配
      • 1.1.2 s = a, p = ., 同样需要用p的第一个字幕去匹配
      • 1.1.3 带*的，这个需要将p的头两个拿去和s匹配：
        • s = a, p1 = .*, p2 = a*,这两种情况，都是满足需要的
        • s = a, p1 = c*.*，那么第一个c*是不匹配的，同样的还有.*是否需要匹配的问题
    • 然后大致的递归思路：
      • 1.1 首先从p的头部分析是哪种子模式
      • 1.2 按照该种子模式匹配
      • 1.3 递归到下层的p和s，这样p和s都因为1.1~1.2的过程中变小了，完成了使用递归解决问题的思路
    • 递归返回？
      • 1.1 s的长度为0？
      • 1.2 p的长度为0？
    • 对于上述过程不清楚的请以下面两个结果作为例子：
      1
      2
      3
      4
      5
      6
      7
      "bcabac"
      "a*a*.*b*b*"
      return: true

      "a"
      ".*..a*"
      return false
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
class Solution {
public:
    bool isMatch(string s, string p) {
        return greadyMatch(s, p);
    }

    bool greadyMatch(string s, string p) {
        int sLen = s.size();
        int pLen = p.size();
        // cout << "sLen & pLen => " << sLen << " " << pLen << s << " " << p << endl;
        if(pLen == 2 && p[0] == '.' && p[1] == '*') {
            return true;
        }

        if(pLen == 1) {
            if(sLen != 1) {
                return false;
            }
            return p[0] == '.' ? true : p[0] == s[0];
        }
        
        if(sLen == 0) {
            if(pLen == 0) {
                return true;
            }
            if(pLen == 2) {
                if(p[1] == '*') {
                    return true;
                }else {
                    return false;
                }
            } else {
                if(p[1] == '*') {
                    return greadyMatch(s, p.substr(2));
                } else {
                    return false;
                }
            }
        }

        if(pLen == 0) {
            return sLen == 0;
        }

        // match as much as possible
        char head0 = p[0];
        char head1 = p[1];
        bool res = false;

        if(p[0] == '.') {
            if(p[1] == '*') {
                // match any len >= 1 of s, when len == 0, then not match
                for(int len = 0; len <= sLen; ++len) {
                    res = res || greadyMatch(s.substr(len), p.substr(2));
                    // cout << "tried: " << s.substr(len) << " " << p.substr(2) << endl;
                }
                return res;
            } else { 
                return greadyMatch(s.substr(1), p.substr(1));
            }
        } else {
            // p[0] = a~z
            if(p[0] != s[0]) {
                if(p[1] == '*') {
                    // cout << p.substr(2) << "\nculled!" <<endl;
                    return greadyMatch(s, p.substr(2));
                } else {
                    return false;
                }
            } else {

                if(p[1] == '*') {
                    int sameLen = s.find_first_not_of(p[0]);
                    if(sameLen == -1) {
                        sameLen = sLen;
                    }
                    // cout << "sameLen2 -> " << sameLen << s.substr(1) << p.substr(2) << endl;
                    // when len = 0, not use this * to match
                    for(int len = 0; len <= sameLen; ++len) {
                        res = res || greadyMatch(s.substr(len), p.substr(2));
                    }
                    return res;
                } else {
                    return greadyMatch(s.substr(1), p.substr(1));
                }
            }
            
        }
        
        // never be executed
        return res;
    }
};

2 二叉搜索树(平衡意味着任意两个子树高度差不应该大于1)

1373 maxSumBST 二叉搜索子树的最大键值和

1 题目

https://leetcode-cn.com/problems/maximum-sum-bst-in-binary-tree/

2 解题思路

  • 1 采用后续遍历，(前中后遍历的前中后是针对root节点的访问时期和左右子树的比较)
  • 2 对于每个节点，维持该节点的4个值：
    • int sum = 0; // 子树的所有和
    • int isBST = false; // 该节点为root的子树是否为BST
    • int maxVal = INT_MIN; // 该节点对应子树最大值
    • int minVal = INT_MAX; // 该节点对应子树最小值
      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
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      /**
       * 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:
          struct entry {
              int sum = 0;
              int isBST = false;
              int maxVal = INT_MIN;
              int minVal = INT_MAX;
              entry() {};
          };
          map<void*, entry> bstRec;

          void dfs(TreeNode* root, int& res) {
              if(nullptr == root) {
                  return;
              }
              dfs(root->left, res);
              dfs(root->right, res);

              // curRoot
              entry tmp;
              if(nullptr != root->left && nullptr != root->right) {
                  tmp.sum = root->val + bstRec[root->right].sum + bstRec[root->left].sum;
                  tmp.isBST = bstRec[root->right].isBST && \ 
                      root->val < bstRec[root->right].minVal && \
                      root->val > bstRec[root->left].maxVal;
                  tmp.maxVal = max(root->val, bstRec[root->left].maxVal);
                  tmp.maxVal = max(tmp.maxVal, bstRec[root->right].maxVal);
                  tmp.minVal = min(root->val, bstRec[root->left].minVal);
                  tmp.minVal = min(tmp.minVal, bstRec[root->right].minVal);
              } else if(nullptr == root->left && nullptr != root->right) {
                  tmp.sum = root->val + bstRec[root->right].sum;
                  tmp.isBST = bstRec[root->right].isBST && root->val < bstRec[root->right].minVal;
                  tmp.maxVal = max(root->val, bstRec[root->right].maxVal);
                  tmp.minVal = min(root->val, bstRec[root->right].minVal);
              } else if(nullptr != root->left && nullptr == root->right) {
                  tmp.sum = root->val + bstRec[root->left].sum;
                  tmp.isBST = bstRec[root->left].isBST && root->val > bstRec[root->left].maxVal;
                  tmp.maxVal = max(root->val, bstRec[root->left].maxVal);
                  tmp.minVal = min(root->val, bstRec[root->left].minVal);
              } else {
                  tmp.sum = root->val;
                  tmp.isBST = true;
                  tmp.maxVal = root->val;
                  tmp.minVal = root->val;
              } 
              if(tmp.isBST) {
                  res = max(res, tmp.sum);
              } 
              // cout << root->val << " -> " << tmp.sum << endl;;
              bstRec[root] = tmp;

          }

          int maxSumBST(TreeNode* root) {
              int res = 0;
              dfs(root, res);
              return res;
          }
      };

1569. 将子数组重新排序得到同一个二叉查找树的方案数

1 题目

https://leetcode-cn.com/problems/number-of-ways-to-reorder-array-to-get-same-bst/

2 解题思路

  • 1 阅读提示即可，大致思路如下：
    • 1.1 首先，意识到第一个数必然为二叉树的root，那么找出左边的节点和右边的节点分别记为lt，和rt
    • 1.2 首先假设我们知道了以lt和rt的不改变子树结构的重排序方案数字为findWays(lt), findWays(rt)
    • 1.3 那么我们只需要思考，如何利用1.2的结果来获得当前root的结果：
      • 很显然，我们只需要确定lt和rt在root对应的整个序列(长度记录为n)中放置方法有多少种方案？进一步分析：在不改变lt序列内部相对顺序的情况下，找出有多少繁殖lt序列的方法？那么不就是n-1中选出lt长度记为k个位置的方法数字吗？
      • 上述答案显而易见： c(n-1, k) = (n-1)!/(n-1-k)!/(k)!;
  • 2 接着就是大数问题：由于n最大为1000，它的阶乘显然溢出，于是上面的直接计算阶乘的方案就失效，采用动动态规划的方法去算阶乘：
    • c(n, k) = c(n-1, k) + c(n-1, k-1)
    • 直观上来看假设原来只有n-1个物品选择k个，现在多加了一个物品，还是选择k个，那么方案数增加了：从 n 个物品中选择 k 个的方案数，等于从前 n-1 个物品中选择 k 个的方案数，加上从前 n-1 个物品中选择 k-1个（再选上第 nn 个物品）的方案数之和。
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
57
58
59
60
61
62
63
64
65
66
67
68
class Solution {
public:
    static constexpr long long largePrime = 1000000007;
    
    vector<long long> factorial;
    
    vector<vector<int>> c;

    int numOfWays(vector<int>& nums) {
        long long ans = 0;
        int n = nums.size();
        factorial.resize(1000, 1);
        // for(long long i = 1; i < 1000; ++i) {
        //     factorial[i] = i * (factorial[i-1] % largePrime);
        //     // cout << i << "->" << factorial[i] << endl;
        //     factorial[i] %= largePrime;
        // }
        
        c.assign(n, vector<int>(n));
        c[0][0] = 1;
        // cal c(n, m) = c(n-1, m) + c(n-1, m-1);
        for(int i = 1; i < n; ++i) {
            c[i][0] = 1;
            for(int j = 1; j < n; ++j) {
                c[i][j] = (c[i-1][j] + c[i-1][j-1]) % largePrime;
            }
        }
        
        ans = findWays(nums);

        return ans - 1;
    }

    long long findWays(vector<int>& nums) {
        int n = nums.size();
        if(n <= 2) {
            return 1;
        }
        
        int root = nums[0];
        vector<int> left;
        vector<int> right;
        for(int i = 1; i < nums.size(); ++i) {
            if(nums[i] < root) {
                left.emplace_back(nums[i]);
            } else {
                right.emplace_back(nums[i]);
            }
        }
        
        // that means:
        // for the left tree, all nodes shall seat in the other places(and not change the relative order)
        // except root pos find the way out(the way shall equal: 
        //     pick nodes size seat from all seats, that is c(n, m-1);
        // ) and mutiply the two subTree arrange way num
        int seats = n - 1;
        int nodesToSeat = left.size();
        // cout << "c(n, k) " << seats << " -> " << nodesToSeat << " = " << c[seats][nodesToSeat] << endl;
        // cout << "l r : " << findWays(left) << "  " << findWays(right) << endl;
        // return ((findWays(left)  % largePrime )* (findWays(right) % largePrime)) * (getWaysForCurLevel(seats, nodesToSeat) % largePrime);
        return findWays(left)  % largePrime * findWays(right) % largePrime * c[seats][nodesToSeat] % largePrime;
    }

    long long getWaysForCurLevel(int seats, int nodesToSeat) {
        cout << "c(n, k)2 :" << factorial[seats] << " " << factorial[nodesToSeat] << " " << factorial[seats - nodesToSeat] << endl;; 
        return factorial[seats] / factorial[nodesToSeat] / factorial[seats - nodesToSeat];
    }
};

0095. 不同的二叉搜索树 II

1 题目

https://leetcode-cn.com/problems/unique-binary-search-trees-ii/

2 解题思路

  • 1 首先明确一点，递归的主体为，从nums的数组中返回对应的所有可能的bst树
    • 1.1 输入： vector
    • 1.2 返回： vector<treeNode*>
  • 2 于是递归思路的想法就来了：
    • 2.1 对于一个node如何生成其所有可能的二叉树呢？我们只考虑第1层到第2层的(因为其他所有层的递归都是一样的逻辑，除非返回层不太一样)
      • 2.1.1 从nums中选择一个作为root，左边的numsLeft和右边的numsRight分别获取root的所有左右子树
      • 2.1.2 递归调用函数从numsLeft得到leftTrees，相应的得到rightTrees
      • 2.1.3 得到leftTrees和rightTrees以后，采用2层for循环和root拼装，得到最后的树
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
/**
 * 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) {
        vector<int> nodes;
        for(int i = 0; i < n; ++i) {
            nodes.emplace_back(i+1);
        }
        vector<TreeNode*> res;
        return getTreesFromArray(nodes);
    }

    vector<TreeNode*> getTreesFromArray(vector<int>& nodes) {
        int n = nodes.size();
        vector<TreeNode*> tmpRes;
        if(0 == n) {
            return {nullptr};
        }
        for(int i = 0; i < n; ++i) {
            int rootVal = nodes[i];
            vector<int> tmpLeft(nodes.begin(), nodes.begin() + i);
            vector<int> tmpRight(nodes.begin() + i + 1, nodes.end());
            vector<TreeNode*> left = getTreesFromArray(tmpLeft);
            vector<TreeNode*> right = getTreesFromArray(tmpRight);
            for(int m = 0; m < left.size(); ++m) {
                for(int n = 0; n < right.size(); ++n) {
                    TreeNode* root = new TreeNode(rootVal, left[m], right[n]); 
                    tmpRes.emplace_back(root); 
                }
            }
        }
        return tmpRes;
    }
}

0000 面试题 04.09. 二叉搜索树序列

1 题目

https://leetcode-cn.com/problems/bst-sequences-lcci/

2 解题思路

  • 1 首先明确一点，递归的主体为，从root对应的tree中获取所有可能的bst子树序列
    • 1.1 输入： treeNode*
    • 1.2 返回： vector<vector>
  • 2 于是递归思路的想法就来了：
    • 2.1 对于一个root如何生成其所有可能的二叉树序列呢？我们只考虑第1层到第2层的(因为其他所有层的递归都是一样的逻辑，除非返回层不太一样)

经典写法：

1
2
3
4
5
6
7
8
9
10
11
void selectKFromN(int st, int k, vector<vector<int>>& res, vector<int>& nums, vector<int>& tmpRes) {
    if(k == 0) {
        res.emplace_back(tmpRes);
        return;
    }
    for(int i = st; i < nums.size() - k + 1; ++i) {
        tmpRes.emplace_back(nums[i]);
        selectKFromN(i + 1, k - 1, res, nums, tmpRes);
        tmpRes.pop_back();
    }
}
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/**
 * 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:
    vector<vector<int>> BSTSequences(TreeNode* root) {
        return getSequencesFromRoot(root);
    }

    vector<vector<int>> getSequencesFromRoot(TreeNode* root) {
        if(nullptr == root) {
            return {{}};
        }
        
        vector<vector<int>> sequences;
        // for(auto seq : s) {
        //     s.emplace_back(root->val);
        // }
        // get left sequences and right
        vector<vector<int>> lSeqs = getSequencesFromRoot(root->left);
        vector<vector<int>> rSeqs = getSequencesFromRoot(root->right);
        int lSize = lSeqs[0].size();
        int rSize = rSeqs[0].size();
        
        // cout << "d0" << endl;
        // select lSize's positions in lSize + rSize + 1 's vector
        vector<vector<int>> res;
        vector<int> nums;
        for(int i = 0; i < lSize + rSize; ++i) {
            nums.emplace_back(i+1);
        }
        vector<int> tmpRes;
        // cout << "d1" << endl;
        selectKFromN(0, lSize, res, nums, tmpRes);
        
        int seqLen = lSeqs[0].size() + rSeqs[0].size() + 1;
        // cout << "d2 " << lSize << "@" << rSize << "=" << seqLen << endl;
            
        for(auto & lSeq : lSeqs) {
            for(auto & rSeq : rSeqs) {
                
                // cout << "d3" << endl;
                vector<int> tmpSeq(seqLen);
                tmpSeq[0] = root->val;

                for(auto & idxVecForLeft : res) {
                    int curLeft = 0;
                    int curRight = 0;
                    int lastLeft = 1;
                    vector<bool> forRight(seqLen, true);
                    
                    // cout << "d4" << endl;
                    for(auto lIdx : idxVecForLeft) {
                        tmpSeq[lIdx] = lSeq[curLeft++];
                        forRight[lIdx] = false;
                    }
                    for(int i = 1; i < seqLen; ++i) {
                        if(forRight[i]) {
                            tmpSeq[i] = rSeq[curRight++];
                        }
                    }
                    sequences.emplace_back(tmpSeq);
                }
            }
        }

        return sequences;
    }

    void selectKFromN(int st, int k, vector<vector<int>>& res, vector<int>& nums, vector<int>& tmpRes) {
        if(k == 0) {
            res.emplace_back(tmpRes);
            return;
        }
        for(int i = st; i < nums.size() - k + 1; ++i) {
            tmpRes.emplace_back(nums[i]);
            selectKFromN(i + 1, k - 1, res, nums, tmpRes);
            tmpRes.pop_back();
        }
    }
}