algo-aha

二叉树的前序遍历串是否合法

• https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/

bool isValidSerialization(string preorder) {
    // 想象扫描串并构建树，在扫描串的过程中要确保"叶节点数<内节点数+1"，
    // 一旦"叶节点数=内节点数+1"则树已构建好不能再扩展，要确保扫描完。
    // 设diff=叶节点数-内节点数，扫描过程中确保diff<1，一旦diff==1确保扫描完。
    const int N = preorder.size();
    int diff = 0, i = 0;
    while (i < N) {
        if (preorder[i++] == '#') diff++;
        else diff--;
        if (diff == 1) break;

        // 向前直到','
        while (i < N && preorder[i] != ',') i++;
        if (i < N) i++;
    }
    return i == N && diff == 1;
}

扩展：bst前序遍历数组是否合法

可交换节点的左右子树，为使前序遍历结果符合给定顺序，要在哪些节点做交换

• https://leetcode.com/problems/flip-binary-tree-to-match-preorder-traversal/

vector<int> flipMatchVoyage(TreeNode* root, vector<int>& voyage) {
    vector<int> ans; 
    int idx = 0; // 类似表达式解析问题，有个idx记录解析位置
    if (match(root, voyage, idx, ans)) return ans;
    return {-1};
}

bool match(TreeNode* root, vector<int>& voyage, int &idx, vector<int> &ans) {
    if (!root) return true;
    if (root->val != voyage[idx++]) return false;
    if (root->left && root->left->val != voyage[idx]) {
        ans.push_back(root->val); // flip
        return match(root->right, voyage, idx, ans) 
            && match(root->left, voyage, idx, ans);
    }
    return match(root->left, voyage, idx, ans) 
        && match(root->right, voyage, idx, ans);            
}

扩展：从前序遍历数组构造bst