原题

LintCode 691. BST Swapped Nodes

Description

In a binary search tree, (Only) two nodes are swapped. Find out these nodes and swap them. If there no node swapped, return original root of tree.

Example

Given a binary search tree:

    4
   / \
  5   2
 / \
1   3

return

    4
   / \
  2   5
 / \
1   3

解题

题意是一棵二叉搜索树有两个节点被交换了，找到这两个节点，换回来。

思路：中序遍历二叉树，本来应该得到一个正序的数组，但是其中有两个数字的顺序是错误的。直接交换这两个数字就行了。

代码

class Solution {
public:
    /*
    * @param : the given tree
    * @return: the tree after swapping
    */
    TreeNode * bstSwappedNode(TreeNode * root) {
        helper(root);
        vector<TreeNode*> v;
        for (int i = 0; i < vec.size(); i++) {
            if (i > 0) {
                if (vec[i].first < vec[i - 1].first) {
                    v.push_back(vec[i].second);
                }
            }
            if (i < vec.size() - 1) {
                if (vec[i].first > vec[i + 1].first) {
                    v.push_back(vec[i].second);
                }
            }
        }
        if (v.size())
            swap(v.front()->val, v.back()->val);
        return root;
    }
private:
    vector<pair<int, TreeNode*>> vec;
    void helper(TreeNode * root) {
        if (!root) return;
        helper(root->left);
        vec.push_back({ root->val, root });
        helper(root->right);
    }
};