题解 | 恢复二叉搜索树

题干分析:

题目要求我们针对一个只有两个节点发生错误互换的二叉搜索树进行修复.

二叉搜索树定义如下：

• 节点的左子树只包含 严格小于 当前节点的数。
• 节点的右子树只包含 严格大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

针对二叉搜索树,其中序遍历序列应为一个严格递增序列.

依题意得,这个二叉搜索树有且仅有两个节点发生了互换,因此中序遍历序列应当也只有两个序列值不符合严格递增规定.

算法思路:

我们只需针对两个不符合严格递增节点进行值互换即可,但注意这两个节点是否相邻有两种情况:

情况1:不相邻: 例如中序序列为 1, 8, 3, 4, 5, 6, 7, 2, 9,其中2与8发生了互换,中序遍历时会发现两次相邻逆序情况(8,3)与(7,2)

情况2:相邻: 例如中序序列为1, 2, 4, 3, 5, 6, 7, 8, 9, 其中3与4发生了互换,中序遍历时只会发现一次相邻逆序情况(4,3)

针对这两种情况,算法思路如下:

中序遍历的过程中记录第一次发生逆序的当前节点与上一节点,继续中序遍历,如果遍历到第二个逆序情况,将保存的第一个节点值与当前节点值进行互换,后续无需再遍历;如果整个遍历过程中只发现一次逆序,遍历完成后交换两个保存的节点中的值.

实现代码:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    bool end = false;
    TreeNode *pre = nullptr; // 遍历前一节点
    TreeNode *tar1 = nullptr; // 目标节点1
    TreeNode *tar2 = nullptr; // 目标节点2

    void dfs(TreeNode *node) {
        if (!end && node) {
            dfs(node->left);
            if (pre && pre->val >= node->val) {
                if (!tar1) {
                    tar1 = pre;
                    tar2 = node;
                }
                else {
                    int tmp = tar1->val;
                    tar1->val = node->val;
                    node->val = tmp;
                    end = true;
                }
            }
            pre = node;
            dfs(node->right);
        }
    }
public:
    void recoverTree(TreeNode* root) {
        dfs(root);
        if (!end) {
            int tmp = tar1->val;
            tar1->val = tar2->val;
            tar2->val = tmp;
        }
    }
};

复杂度分析:

针对节点数为n的符合题目要求的二叉树:

• 遍历每个节点并进行操作,时间复杂度为O(n)
• 针对每个节点进行递归操作,递归消耗空间复杂度为O(n)(最坏情况下二叉树退化为一条链)