LeetCode 99. Recover Binary Search Tree [Hard] [C++] 解題筆記

這題給我們一個錯的 binary tree (tree 的某兩個 node 被交換了導致該 tree 不符合 binary tree 的性質)，要求我們修正這個 tree 並不改變其結構。

EX:

        Input: [3,1,4,null,null,2]

      3
     / \
    1   4
       /
      2

    Output: [2,1,4,null,null,3]

      2
     / \
    1   4
       /
      3

想法:

    這題基本上也是可以用 inorder traversal 的思路，在 traverse 過程中若當前節點的值若小於中序順序的

前一個值，表示這兩個值應該要交換，這題困難點在於 follow up 要求要在 O(1) space 限制下完成，一般 inorder traversal

的實作方式都必須用到 stack 勢必需要 O(n) space 才能完成，因此要達到 O(1) space 就必須使用 Morris Traversal 。

Complexity: O(n) time, O(n)/O(1) space.

完整程式碼:

解法一(recursive):

class Solution {
public:
    TreeNode* firstelement;
    TreeNode* secondelement;
    TreeNode* prevelement;
    void inorderTraverse(TreeNode* root) {
        if (root == NULL) { return; }
        inorderTraverse(root->left);
        if (prevelement) {
            if (firstelement == NULL && prevelement->val >= root->val) {
                firstelement = prevelement;
            }
            if (firstelement != NULL && prevelement->val >= root->val) {
                secondelement = root;
            }
        }
        prevelement = root;
        inorderTraverse(root->right);
    }
    void recoverTree(TreeNode* root) {
        if (root == NULL) { return; }
        firstelement = NULL;
        secondelement = NULL;
        prevelement = NULL;
        inorderTraverse(root);
        auto tmp = firstelement->val;
        firstelement->val = secondelement->val;
        secondelement->val = tmp;
    }
};

解法二(Morris Traversal):

class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode* first = nullptr;
        TreeNode* second = nullptr;
        TreeNode* prev = nullptr;
        TreeNode* cur = root;
        while (cur != nullptr) {
            if (cur->left == nullptr) {
                if (prev) {
                    if (first == nullptr && prev->val >= cur->val) {
                        first = prev;
                    }
                    if (first != nullptr && prev->val >= cur->val) {
                        second = cur;
                    }
                }
                prev = cur;
                cur = cur->right;
            }
            else {
                // find predecessor
                TreeNode* pre = cur->left;
                while (pre->right != nullptr && pre->right != cur) {
                    pre = pre->right;
                }
                if (pre->right == nullptr) {
                    pre->right = cur;
                    cur = cur->left;
                }
                // already traverse whole left subtree of cur
                else {
                    pre->right = nullptr;
                    if (prev) {
                        if (first == nullptr && prev->val >= cur->val) {
                            first = prev;
                        }
                        if (first != nullptr && prev->val >= cur->val) {
                            second = cur;
                        }
                    }
                    prev = cur;
                    cur = cur->right;
                }
            }
        }
        // swap
        auto tmp = first->val;
        first->val = second->val;
        second->val = tmp;
        
        return;
    }
};