Recover Binary Search Tree -- leetcode

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?

算法一，中序周遊

遞歸中序周遊時。周遊時，維持一個prev指針，指向目前元素的前一個元素。

找出違反順序的兩個節點。并存儲下來。

違反情況，分成兩種：

1. 相鄰的元素的兩個節點被交換。  這種情況下，在中序周遊中，隻換探測到一次違反 （違反指： 前面節點的值大于目前節點的值）。

2. 不相鄰的元素的兩個節點被交換。 這種情況下，在中序周遊中，将會探到二次違反。

在leetcode上實際執行時間為101ms.

/**
 * 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:
    void recoverTree(TreeNode* root) {
        TreeNode *prev = 0, *first = 0, *second = 0;
        helper(root, prev, first, second);
        swap(first->val, second->val);
    }
    
    void helper(TreeNode *root, TreeNode *&prev, TreeNode *&first, TreeNode *&second) {
        if (!root) return;
        helper(root->left, prev, first, second);
        if (prev && prev->val > root->val) {
            if (!first) {
                first = prev;
                second = root;
            }
            else {
                second = root;
                return;
            }
        }
        prev = root;
        helper(root->right, prev, first, second);
    }
};
           

算法二：Morris周遊

用Morris周遊代替遞歸調用。

其他同上。

在leetcode上實際執行時間為131ms。

時間比算法一長。原因在于，在算法一中，當找到了第二次違反時。就直接進行棧復原了。可能會節省一部分時間。

而Morris，需要恢複被複用的右指針。是以需要周遊到結束。

class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode *first = 0, *second = 0, *prev = 0;
        while (root) {
            if (!root->left) {
                if (prev && prev->val > root->val) {
                    second = root;
                    if (!first) 
                        first = prev;
                }
                prev = root;
                root = root->right;
            }
            else {
                TreeNode *p = root->left;
                while (p->right && p->right != root)
                    p = p->right;
                
                if (!p->right) {
                    p->right = root;
                    root = root->left;
                }
                else {
                    p->right = 0;
                    if (prev && prev->val > root->val) {
                        second = root;
                        if (!first) 
                            first = prev;
                    }
                    prev = root;
                    root = root->right;
                }
            }
        }
        if (first && second)
            swap(first->val, second->val);
    }
};