博文中会简要介绍Leetcode P0099题目分析及解题思路。
“Recover Binary Search Tree”是一道比较经典的考察二叉搜索树（Binary Search Tree，BST）性质的问题。关于BST的性质，我们知道对于在BST上的任意一个树结点，其值要大于它左子树的最大值，小于其右子树的最小值，而且它的中序遍历后的序列是一个递增序列。根据这些性质我们就可以还原一个二叉搜索树。
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Example 1:
Input: [1,3,null,null,2] 1 / 3 \ 2 Output: [3,1,null,null,2] 3 / 1 \ 2
最基本的思路是，先通过中序遍历得到一个数组，根据BST的性质，这个数组本应该是递增有序的数组，但是由于我们调换了其中两个树结点的值，在现在这个数组中将会存在最多两个极大值点或者说极小值点（不含两端），假设为k个。我们很容易地可以发现，第1个极大值点的值和第k-1个极小值点的值是被调换的两个值，那么我们得到这两个树结点以后，再调换值即可还原二叉搜索树。
以下是Java的题解代码实现。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public void recoverTree(TreeNode root) {
Deque<TreeNode> stack = new LinkedList<>();
List<TreeNode> orderedSequence = new ArrayList<>();
TreeNode curr = root;
// Iterative
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.offerFirst(curr);
curr = curr.left;
}
curr = stack.pollFirst();
orderedSequence.add(curr);
curr = curr.right;
}
TreeNode big = null, small = null;
int size = orderedSequence.size();
for (int itr=0; itr<size-1; ++itr) {
if (orderedSequence.get(itr).val < orderedSequence.get(itr+1).val)
continue;
if (big == null) {
big = orderedSequence.get(itr);
small = orderedSequence.get(itr+1);
}
else
small = orderedSequence.get(itr+1);
}
int temp = big.val;
big.val = small.val;
small.val = temp;
}
}
以下是C++的题解代码实现。
/**
* 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:
void recoverTree(TreeNode* root) {
stack<TreeNode*> nodes;
vector<TreeNode*> ordered_nodes;
TreeNode *curr = root;
while (curr != NULL || !nodes.empty()) {
while (curr != NULL) {
nodes.push(curr);
curr = curr->left;
}
curr = nodes.top();
nodes.pop();
ordered_nodes.push_back(curr);
curr = curr->right;
}
TreeNode *big = NULL, *small = NULL;
for (int itr=0; itr<ordered_nodes.size()-1; ++itr) {
if (ordered_nodes[itr]->val < ordered_nodes[itr+1]->val)
continue;
if (big == NULL) {
big = ordered_nodes[itr];
small = ordered_nodes[itr+1];
}
else
small = ordered_nodes[itr+1];
}
swap(big->val, small->val);
}
};