• 关键字:二叉搜索树、深度优先搜索
  • 难度:难
  • 前置知识:二叉搜索树
  • 题目大意:一棵二叉搜索树中的两个结点的值被意外交换了,现在希望你能够用O(1)的空间复杂度,将这棵二叉搜索树还原到其原本的样子

题目描述

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

Recover the tree without changing its structure.

解法

对于这道题目,我们不妨先看看,如果将一个有序数组中的两个元素进行交换了,如何找出这两个数?(找到后还原是简单的)

如对于数组1,2,7,4,5,6,3,8,9,如何判断是哪两个元素发生了交换呢?

不难发现,新的数组中存在两对逆序并相邻的数字,即7,46,3,造成这出现的原因,正是发生了一次交换,由于一定是较小的数换到了较大数的位置(向后),较大的数换到了较小数的位置(向前)。所以在这两对中,我们可以简单的判断出:是前一对的较大数和后一对的较小数发生了交换

当然存在一些特殊情况,最简单的就是1,2,4,3,5,6,只存在一对逆序,这是因为交换的两个数本身是相邻的,对于这种情况,我们进行分类讨论与判断即可。

// 用于存储当前找到的发生交换的数
int first = -1, second;
// 从前往后依次寻找逆序并相邻的数字对
for (int i = 0; i < n; i++) {
    // 存在逆序
    if (i > 0 && val[i] < val[i - 1]) {
        // 如果当前一对都没有找到
        if (first == -1) {
            // 不放先假设只有一对
            first = i - 1; second = i;
        }
        else {
            // 存在两对,只需要修改second
            second = i;
        }
    }
}
// Swap(val[first], val[second])

现在,数组上的问题得到了解决,那么如何在二叉搜索树上解决类似的问题呢?

实际上也是简单的,由于二叉搜索树的中序遍历实际上就是按照从小到大的顺序依次枚举每个元素,所以只需要使用一次深度优先搜索,我们就可以向数组一样的访问二叉搜索树的每一个元素,即

void dfs(root) {
    dfs(root -> left)
    // 仿照数组的算法处理root -> val与prev
    prev = root -> val 
    dfs(root -> right)
}

这样一来,我们就可以将数组上的算法套用在二叉搜索树上,找到发生交换的两个位置,最后再将它们交换回来就可以完成题目的要求。

参考代码

/**
 * 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 {
public:
    TreeNode *first, *second, *prev;
    void recoverTree(TreeNode* root) {
        // first和second用于记录发生交换的位置、prev用于记录“数组”中的上一个元素
        first = second = prev = NULL;
        // 中序遍历
        dfs(root);
        // 进行交换
        if (first != NULL && second != NULL) {
            int tmp = first -> val;
            first -> val = second -> val;
            second -> val = tmp;
        }
    }
    void dfs(TreeNode* root) {
        // 左子树
        if (root -> left != NULL) dfs(root -> left);
        // 如果存在逆序
        if (prev != NULL && prev -> val > root -> val) {
            // 这一部分运算使用了一些小技巧,本质上和正文中描述的是等价的
            if (first == NULL) {
                first = prev;
            }
            if (first != NULL) {
                second = root;
            }
        }
        // 当前节点变成“上一个”节点
        prev = root;
        // 右子树
        if (root -> right != NULL) dfs(root -> right);
    }
};

登录发表评论 注册

反馈意见