leetcode 随笔 Recover Binary Search Tree

Recover Binary Search Tree

这个题很有意思，乍一看没什么思路，仔细想一想其实这是一道深度优先搜索的问题。

本身这棵树是按照中序遍历的从小到大生成的，那么我们在解析这颗树的时候如果利用dfs生成中序遍历的数列也应是从小到大依次排列好的。

题目已经给出了只有两对节点是需要互换的，如果我们把中序遍历的结果拿出来，以123456为例，会出现两种结果，第一种是123 54 6 这种连续的，另一种是 12 543 6这种不连续的互换节点。

class Solution {
public:TreeNode *s1=nullptr, *s2=nullptr, *last = new TreeNode(INT_MIN);void recoverTree(TreeNode* root) {bst(root);swap(s1->val, s2->val);}void bst(TreeNode *root){if (root == nullptr)return;bst(root->left);//print value;if (s1==nullptr&&last->val>=root->val){s1 = last;s2 = root;}if (s1 != nullptr&&last->val >= root->val){s2 = root;}last = root;bst(root->right);}
};