恢复BST

recoverBST.md

Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

中序遍历BST，设置一个prev指针，记录当前节点中序遍历时的前节点，如果当前节点大于prev节点的值，说明需要调整次序。用一个pair保存prev和cur

	/**
	 * Definition for binary tree
	 * struct TreeNode {
	 *     int val;
	 *     TreeNode *left;
	 *     TreeNode *right;
	 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	 * };
	 */
	class Solution {
	public:
	    void recoverTree(TreeNode *root) {
	        TreeNode *prev = nullptr;
	        pair<TreeNode*,TreeNode*> dirt(nullptr,nullptr);
	        inorderTraverse(root,&prev,dirt);
	        if(dirt.first && dirt.second){
	            swap(dirt.first->val,dirt.second->val);
	        }
	    }
	    /**
	     * In case of nullptr ,using **pointer args
	     **/
	    void inorderTraverse(TreeNode *root,TreeNode **prev,pair<TreeNode*,TreeNode*>& dirt){
	        if(!root){
	            return;
	        }
	        if(root->left){
	            inorderTraverse(root->left,prev,dirt);
	        }
	        if((*prev) != nullptr && root->val < (*prev)->val){
	            if(dirt.first == nullptr){
	                dirt.first = *prev;
	            }
	            dirt.second = root;
	        }
	        *prev = root;
	        if(root->right){
	            inorderTraverse(root->right,prev,dirt);
	        }
	    }
	};