本文共 943 字，大约阅读时间需要 3 分钟。

题目：

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?

思路：

这道题要求我们复原一个二叉搜索树，说是其中有两个的顺序被调换了，题目要求上说O(n)的解法很直观，这种解法需要用到递归，用中序遍历树，并将所有节点存到一个一维向量中，把所有节点值存到另一个一维向量中，然后对存节点值的一维向量排序，在将排好的数组按顺序赋给节点。

实现代码如下：

// O(n) space complexityclass Solution {public:    void recoverTree(TreeNode *root) {        vector
   
     list;        vector
    
      vals;        inorder(root, list, vals);        sort(vals.begin(), vals.end());        for (int i = 0; i < list.size(); ++i) {            list[i]->val = vals[i];        }    }    void inorder(TreeNode *root, vector
     
       &list, vector
      
        &vals) {        if (!root) return;        inorder(root->left, list, vals);        list.push_back(root);        vals.push_back(root->val);        inorder(root->right, list, vals);    }};
      
     
    
   

转载地址：http://yxuoi.baihongyu.com/