99. Recover Binary Search Tree

Given an input string (`s`) and a pattern (`p`), implement wildcard pattern matching with support for `'?'` and `'*'` where:

• `'?'` Matches any single character.
• `'*'` Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Example 1:

```Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
```

Example 2:

```Input: s = "aa", p = "*"
Output: true
Explanation: '*' matches any sequence.
```

Example 3:

```Input: s = "cb", p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
```

Example 4:

```Input: s = "adceb", p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
```

Example 5:

```Input: s = "acdcb", p = "a*c?b"
Output: false
```

Constraints:

• `0 <= s.length, p.length <= 2000`
• `s` contains only lowercase English letters.
• `p` contains only lowercase English letters, `'?'` or `'*'`.

99. Recover Binary Search Tree
``````struct Solution;
use rustgym_util::*;
use std::mem::swap;

trait Inorder {
}

if let Some(node) = self {
let node = node.borrow();
node.left.inorder(prev, first, second);
if let Some(prev_val) = prev.clone() {
if prev_val.borrow().val >= node.val {
if first.is_none() {
*first = prev.clone();
}
*second = self.clone();
}
}
*prev = self.clone();
node.right.inorder(prev, first, second);
}
}
}

impl Solution {
let mut prev = None;
let mut first = None;
let mut second = None;
root.inorder(&mut prev, &mut first, &mut second);
swap(
&mut first.unwrap().borrow_mut().val,
&mut second.unwrap().borrow_mut().val,
)
}
}

#[test]
fn test() {
let mut root = tree!(1, tree!(3, None, tree!(2)), None);
Solution::recover_tree(&mut root);
let res = tree!(3, tree!(1, None, tree!(2)), None);
assert_eq!(root, res);
let mut root = tree!(3, tree!(1), tree!(4, tree!(2), None));
Solution::recover_tree(&mut root);
let res = tree!(2, tree!(1), tree!(4, tree!(3), None));
assert_eq!(root, res);
}
``````