algo-aha

bst中序遍历的下个节点

• https://leetcode.com/problems/inorder-successor-in-bst/

TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
    if (!root || !p) return NULL;
    // bst的中序遍历是个有序数组，这题相当于要找第一个>p.val的节点
    // 类似二分搜索，root就是二分搜索中的mid
    TreeNode *succ = NULL;
    while (root) {
        if (root->val > p->val) { // root作候选，看左边有没更小的
            succ = root;
            root = root->left;
        } else { // root值太小，排除root和左子树
            root = root->right;
        }
    }
    return succ;
}

bst中删除值为key的节点

• https://leetcode.com/problems/delete-node-in-a-bst/

TreeNode* deleteNode(TreeNode* root, int key) {
	if (!root) return nullptr;
	if (key < root->val) {
		root->left = deleteNode(root->left, key);
		return root;
	} 
	if (key > root->val) {
		root->right = deleteNode(root->right, key);
		return root;
	} 
	
	if (!root->right) {
		auto left = root->left;
		delete root;
		return left;
	}
	// 找到后继节点
	auto succ = root->right;
	while (succ->left) {
		succ = succ->left;
	}
	succ->left = root->left;
	auto right = root->right;
	delete root;
	return right;
}

已知数组从左到右扫描所得的bst样子，求对应数组的可能排列数

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

class Solution {
    vector<vector<int>> C;
    const int MOD = 1e9 + 7;
public:
    int numOfWays(vector<int>& nums) {
        const int N = nums.size();
        // 组合数nCk为杨辉三角中C[n][k]
        C = vector<vector<int>>(N, vector<int>(N));
        C[0][0] = 1;
        for (int i = 1; i < N; i++) {
            C[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
            }
        }
        return ways(nums) - 1; // 其他排列
    }

    int ways(vector<int>& nums) {
        const int N = nums.size();
        if (N <= 1) return 1;

        vector<int> left, right;
        for (int i = 1; i < N; i++) {
            if (nums[i] < nums[0]) left.push_back(nums[i]);
            else right.push_back(nums[i]);
        }
        return weave(left, right);
    }

    int weave(vector<int>& A, vector<int>& B) {
        // 左右两数组交织，可保持二叉树不变
        int nCk = C[A.size() + B.size()][A.size()];
        long left = ways(A), right = ways(B);
        return (((left * right) % MOD) * nCk) % MOD;
    }
};

已知数组从左到右扫描所得的bst样子，求对应数组的所有可能排列

根节点是数组首元素，左子树是小于它的元素们、右子树是大于它的元素们，但左右子树的元素哪个先对应到数组元素不确定。左右子树分别对应的数组有多种排列，取左子树的一组排列{a1, a2, a3, ...}和右子树的一组排列{b1, b2, b3, ...}，怎么由它们得到原数组的排列？用"交织"操作：保持组内的相对次序不变，组间的次序（先插入左子树元素还是右子树元素）无所谓。递归：取{a1}，后面是{a2, a3, ...}和{b1, b2, b3, ...}的交织；或取{b1}，后面是{a1, a2, a3, ...}和{b2, b3, ...}的交织；当一组为空时，另一组直接拼上。见ctci p262。

// 简写起见，List指LinkedList<Integer>，List[]指ArrayList<LinkedList<Integer>>
void weaveLists(List prefix, List l1, List l2, List[] ans) {
    if (l1.size() == 0 || l2.size() == 0) {
        List list = prefix.clone();
        list.add(l1);
        list.add(l2);
        ans.add(list);
        return;
    }

    // l1取头放到prefix中，递归后还原
    int f1 = l1.removeFirst();
    prefix.addLast(f1);
    weaveList(prefix, l1, l2, ans);
    prefix.removeLast();
    l1.addFirst(f1);
    // l2一样处理
    int f2 = l2.removeFirst();  
    prefix.addLast(f2);
    weaveList(prefix, l1, l2, ans);
    prefix.removeLast();
    l2.addFirst(f2);
}

List[] allSequences(TreeNode node) {
    List[] ans = new ArrayList<LinkedList<Integer>>();
    if (!node) return ans;

    List prefix = new LinkedList<Integer>();
    prefix.add(node.data); // 根节点=>数组首元素

    List[] leftSeq = allSequences(node.left);
    List[] rightSeq = allSequences(node.right);
    for (List left : leftSeq) {
        for (List right : rightSeq) {
            weaveList(prefix, left, right, ans);
        }
    }
    return ans;
}