99. Recover Binary Search Tree
博客专区 > cofama 的博客 > 博客详情
99. Recover Binary Search Tree
cofama 发表于11个月前
99. Recover Binary Search Tree
  • 发表于 11个月前
  • 阅读 3
  • 收藏 0
  • 点赞 0
  • 评论 0

【腾讯云】买域名送云解析+SSL证书+建站!>>>   

原题链接

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?

解题的关键是找到两个错误的节点。由于是二分搜索树,可以比较节点与其父节点或子节点的大小关系,来判断是否有问题。可是,即使找到了某个节点与其子节点的大小关系不符合BST的要求,还要进一步确认到底是该节点有问题还是子节点有问题,就比较麻烦了。所以从树结构中去找是比较麻烦的。BST有一个特性,就是用中序遍历输出节点的话,是一个递增的序列,所以我们可以把树“线性化”再来观察。假如一个BST用中序遍历输出123456,交换3、5节点变成125436,可以观察到,必然形成的局面是,第一个出现的交换节点一定比它的后一个节点大,第二个出现的交换节点一定比它的前一个节点小。

因此,我们可以在中序遍历时用一个变量跟踪前一个输出的节点,当第一次出现前一个节点比当前节点大的情况时,前一个节点就是交换节点;当第二次出现这种情况时,当前节点是交换节点。问题是,一般的中序遍历是递归实现,空间复杂度最坏是O(n),最好也要O(lgn),不符合题目O(1)的要求。我从网上找了下,要实现O(1)的中序遍历只能用Morris Traversal,其实就是线索二叉树的方法。

中序遍历之所以常用递归,是因为遍历完左子树后要回溯到根节点。当一个节点有左子树时,中序遍历输出时它的前一个节点(即前驱节点)是左子树的“最右节点”,通俗点讲就是“右下角”。由于右下角的右子树一定是空的(不然它就不是右下角了),所以可以把它的右指针指向根节点,这样在遍历时就可以回溯到根节点了。为了不改变树的结构,回到根节点后,还要在找到这个右下角,把它的右指针重新赋为空。

class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode* prev = NULL;
        TreeNode* tmp = NULL;
        TreeNode* first = NULL;
        TreeNode* second = NULL;
        while(root!=NULL) {
            if(root->left!=NULL) {
                tmp = root->left;
                while(tmp->right!=NULL && tmp->right!=root) tmp = tmp->right;
                if(tmp->right==NULL) {
                    tmp->right = root;
                    root = root->left;
                }
                else {
                    tmp->right = NULL;
                    //find wrong elements
                    if(first==NULL && prev->val>root->val) first = prev;
                    if(first!=NULL && prev->val>root->val) second = root;
                    prev = root;
                    //end finding
                    root = root->right;
                }
            }
            else {
                //find wrong elements
                if(first==NULL && prev!=NULL && prev->val>root->val) first = prev;
                if(first!=NULL && prev->val>root->val) second = root;
                prev = root;
                //end finding
                root = root->right;
            }
        }
        //swap
        int temp = first->val;
        first->val = second->val;
        second->val = temp;
    }
};

代码中,first、second记录两个交换的节点,prev跟踪前一个遍历的节点。如果当前节点有左子树,在开始左子树遍历前,都要先找到它的前驱节点。如果前驱节点的右指针已经指向当前节点了,说明左子树已经遍历完了,可以处理当前节点并遍历右子树。因为中序遍历是按“左中右”的顺序,所以改变前驱节点的右指针也是符合遍历习惯的。

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 22
码字总数 19162
×
cofama
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: