首页 > 数据结构 > 树形结构 > LeetCode-Recover Binary Search Tree[二叉树]
2014
11-19

LeetCode-Recover Binary Search Tree[二叉树]

Recover Binary Search Tree

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?

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.

Here’s an example:

   1
  / \
 2   3
    /
   4
    \
     5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

标签: Tree Depth-first Search
分析

$O(n)$空间的解法是,开一个指针数组,中序遍历,将节点指针依次存放到数组里,然后寻找两处逆向的位置,先从前往后找第一个逆序的位置,然后从后往前找第二个逆序的位置,交换这两个指针的值。

中序遍历一般需要用到栈,空间也是$O(n)$的,如何才能不使用栈?Morris中序遍历。

代码1

// LeetCode, Recover Binary Search Tree
// Morris中序遍历,时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    void recoverTree(TreeNode* root) {
        pair<TreeNode*, TreeNode*> broken;
        TreeNode* prev = nullptr;
        TreeNode* cur = root;

        while (cur != nullptr) {
            if (cur->left == nullptr) {
                detect(broken, prev, cur);
                prev = cur;
                cur = cur->right;
            } else {
                auto node = cur->left;

                while (node->right != nullptr && node->right != cur)
                    node = node->right;

                if (node->right == nullptr) {
                    node->right = cur;
                    //prev = cur; 不能有这句!因为cur还没有被访问
                    cur = cur->left;
                } else {
                    detect(broken, prev, cur);
                    node->right = nullptr;
                    prev = cur;
                    cur = cur->right;
                }
            }
        }

        swap(broken.first->val, broken.second->val);
    }

    void detect(pair<TreeNode*, TreeNode*>& broken, TreeNode* prev,
            TreeNode* current) {
        if (prev != nullptr && prev->val > current->val) {
            if (broken.first == nullptr) {
                broken.first = prev;
            } //不能用else,例如 {0,1},会导致最后 swap时second为nullptr,
              //会 Runtime Error
            broken.second = current;
        }
    }
};

相关题目
Binary Tree Inorder Traversal


  1. 作者你还想更新吗?网上也都说你1月5号更新呐,现在已经1月5号了,你想怎么样。我们现在感觉你这个完全就是不想更的样子,现在已经过了将近两周了。你要不想更新的话,你跟我们说我们不收藏了也不看啦。那你要还想更新的话那就请你快点我不知道你是有事情啊,还是怎么的

  2. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept