LeetCode: 99. 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, 要求在不改变其结构的情况下恢复这个 BST。

解题思路 —— 中序遍历

由于中序遍历 BST 会产生一个递增序列，因此，此题可转化为求出递增序列中交换位置的两个元素。
记当前节点为 root, 前一个节点为 pre，swappedNode 为交换过的节点, 则:

* 当交换的两个元素相邻时， 当出现 pre->val >= root->val 时(如图)， 交换位置的两个元素就是这两个节点的元素;

• 当交换的两个元素不相邻时, 当第一次出现 pre->val >= root->val 时(如图)，其中一个交换位置的元素是 pre 指向的元素。
  

  当第二次出现 pre->val >= root->val 时(如图)，其中一个交换位置的元素是 root 指向的元素。
  

AC 代码

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
class Solution {
private:
    void recoverTreeRef(TreeNode* root, TreeNode*& pre, vector<TreeNode*>& swappedNode)
    {
        if(root == nullptr) return;

        // 对左子树进行审查
        recoverTreeRef(root->left, pre, swappedNode);

        // 对当前节点的元素进行审查
        if(pre != nullptr && pre->val >= root->val)
        {
            if(swappedNode[0] == nullptr) swappedNode[0] = pre;
            swappedNode[1] = root;
        }
        pre = root;

        // 对右子树进行审查
        recoverTreeRef(root->right, pre, swappedNode);

    }
public:
    void recoverTree(TreeNode* root) {
        TreeNode* pre = nullptr;
        vector<TreeNode*> swappedNode(2, nullptr);

        recoverTreeRef(root, pre, swappedNode);
        swap(swappedNode[0]->val, swappedNode[1]->val);
    }
};