leetcode || 99、Recover Binary Search Tree

problem：

thinking：

（1）空间复杂度O（N）的算法最简单：

使用map<int ,TreeNode *>结构可以不破坏原来二叉树的结构

中序遍历二叉树，将数值保存到数组a,同时将每一个数值对应的结点指针保存到map<int ,TreeNode *>，增序排序得到数组b。a与b对比，在a中找到位置不同的元素x、y

在map<int ,TreeNode *>中找到x、y对应的结点指针，交换val值即可

（2）空间复杂度为O(1)的算法：参考http://www.cnblogs.com/remlostime/archive/2012/11/19/2777859.html

code：

class Solution {
public:
    void treeWalk(TreeNode* root, TreeNode*& prv, TreeNode*& first, TreeNode*& second)
    {
      if(root==NULL)
         return;
      treeWalk(root->left,prv,first,second);
      if((prv!=NULL)&&(prv->val>root->val)){
          if(first==NULL)
             first=prv;
           second=root;
      }
      prv=root;
      treeWalk(root->right,prv,first,second);
    }
  
    void recoverTree(TreeNode *root) {
        TreeNode* first=NULL;
        TreeNode* second=NULL;
        TreeNode* prv=NULL;
        treeWalk(root,prv,first,second);
        int tmp=first->val;
        first->val=second->val;
        second->val=tmp;
    }
};

leetcode || 99、Recover Binary Search Tree

原文：http://blog.csdn.net/hustyangju/article/details/45098909