C++如何實(shí)現(xiàn)LeetCode之復(fù)原二叉搜索樹

這篇文章給大家分享的是有關(guān)C++如何實(shí)現(xiàn)LeetCode之復(fù)原二叉搜索樹的內(nèi)容。小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，一起跟隨小編過(guò)來(lái)看看吧。

[LeetCode] 99. Recover Binary Search Tree 復(fù)原二叉搜索樹

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

Recover the tree without changing its structure.

Example 1:

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

   1
/
3
\
2

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

   3
/
1
\
2

Example 2:

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

3
/ \
1   4
/
2

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

  2
/ \
1   4
/
3

Follow up:

• A solution using O(n) space is pretty straight forward.

• Could you devise a constant space solution?

這道題要求我們復(fù)原一個(gè)二叉搜索樹，說(shuō)是其中有兩個(gè)的順序被調(diào)換了，題目要求上說(shuō) O(n) 的解法很直觀，這種解法需要用到遞歸，用中序遍歷樹，并將所有節(jié)點(diǎn)存到一個(gè)一維向量中，把所有節(jié)點(diǎn)值存到另一個(gè)一維向量中，然后對(duì)存節(jié)點(diǎn)值的一維向量排序，在將排好的數(shù)組按順序賦給節(jié)點(diǎn)。這種最一般的解法可針對(duì)任意個(gè)數(shù)目的節(jié)點(diǎn)錯(cuò)亂的情況，這里先貼上此種解法：

解法一：

// O(n) space complexity
class Solution {
public:
    void recoverTree(TreeNode* root) {
        vector<TreeNode*> list;
        vector<int> vals;
        inorder(root, list, vals);
        sort(vals.begin(), vals.end());
        for (int i = 0; i < list.size(); ++i) {
            list[i]->val = vals[i];
        }
    }
    void inorder(TreeNode* root, vector<TreeNode*>& list, vector<int>& vals) {
        if (!root) return;
        inorder(root->left, list, vals);
        list.push_back(root);
        vals.push_back(root->val);
        inorder(root->right, list, vals);
    }
};

然后博主上網(wǎng)搜了許多其他解法，看到另一種是用雙指針來(lái)代替一維向量的，但是這種方法用到了遞歸，也不是 O(1) 空間復(fù)雜度的解法，這里需要三個(gè)指針，first，second 分別表示第一個(gè)和第二個(gè)錯(cuò)亂位置的節(jié)點(diǎn)，pre 指向當(dāng)前節(jié)點(diǎn)的中序遍歷的前一個(gè)節(jié)點(diǎn)。這里用傳統(tǒng)的中序遍歷遞歸來(lái)做，不過(guò)在應(yīng)該輸出節(jié)點(diǎn)值的地方，換成了判斷 pre 和當(dāng)前節(jié)點(diǎn)值的大小，如果 pre 的大，若 first 為空，則將 first 指向 pre 指的節(jié)點(diǎn)，把 second 指向當(dāng)前節(jié)點(diǎn)。這樣中序遍歷完整個(gè)樹，若 first 和 second 都存在，則交換它們的節(jié)點(diǎn)值即可。這個(gè)算法的空間復(fù)雜度仍為 O(n)，n為樹的高度，參見代碼如下：

解法二：

// Still O(n) space complexity
class Solution {
public:
    TreeNode *pre = NULL, *first = NULL, *second = NULL;
    void recoverTree(TreeNode* root) {
        inorder(root);
        swap(first->val, second->val);
    }
    void inorder(TreeNode* root) {
        if (!root) return;
        inorder(root->left);
        if (!pre) pre = root;
        else {
            if (pre->val > root->val) {
                if (!first) first = pre;
                second = root;
            }
            pre = root;
        }
        inorder(root->right);
    }
};

我們其實(shí)也可以使用迭代的寫法，因?yàn)橹行虮闅v Binary Tree Inorder Traversal 也可以借助棧來(lái)實(shí)現(xiàn)，原理還是跟前面的相同，記錄前一個(gè)結(jié)點(diǎn)，并和當(dāng)前結(jié)點(diǎn)相比，如果前一個(gè)結(jié)點(diǎn)值大，那么更新 first 和 second，最后交換 first 和 second 的結(jié)點(diǎn)值即可，參見代碼如下：

解法三：

// Always O(n) space complexity
class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode *pre = NULL, *first = NULL, *second = NULL, *p = root;
        stack<TreeNode*> st;
        while (p || !st.empty()) {
            while (p) {
                st.push(p);
                p = p->left;
            }
            p = st.top(); st.pop();
            if (pre) {
                if (pre->val > p->val) {
                    if (!first) first = pre;
                    second = p;
                }
            }
            pre = p;
            p = p->right;
        }
        swap(first->val, second->val);
    }
};

這道題的真正符合要求的解法應(yīng)該用的 Morris 遍歷，這是一種非遞歸且不使用棧，空間復(fù)雜度為 O(1) 的遍歷方法，可參見博主之前的博客 Binary Tree Inorder Traversal，在其基礎(chǔ)上做些修改，加入 first, second 和 parent 指針，來(lái)比較當(dāng)前節(jié)點(diǎn)值和中序遍歷的前一節(jié)點(diǎn)值的大小，跟上面遞歸算法的思路相似，代碼如下：

解法四：

// Now O(1) space complexity
class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode *first = nullptr, *second = nullptr, *cur = root, *pre = nullptr ;
        while (cur) {
            if (cur->left){
                TreeNode *p = cur->left;
                while (p->right && p->right != cur) p = p->right;
                if (!p->right) {
                    p->right = cur;
                    cur = cur->left;
                    continue;
                } else {
                    p->right = NULL;
                }  
            }
            if (pre && cur->val < pre->val){
              if (!first) first = pre;
              second = cur;
            }
            pre = cur;
            cur = cur->right;
        }
        swap(first->val, second->val);
    }
};

感謝各位的閱讀！關(guān)于“C++如何實(shí)現(xiàn)LeetCode之復(fù)原二叉搜索樹”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，讓大家可以學(xué)到更多知識(shí)，如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！