首页 > 代码库 > Recover Binary Search Tree

Recover Binary Search Tree

2024-07-14 21:30:41   223人阅读

-----QUESTION-----

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?
-----SOLUTION-----
class Solution {
public:
    void recoverTree(TreeNode *root) {
        vals.clear();
        treeNodes.clear();
        inorderTraverse(root);
        
        sort(vals.begin(), vals.end());
        for (int i = 0; i < treeNodes.size(); ++i)
        {
            treeNodes[i]->val = vals[i];
        }
    }
    
    void inorderTraverse(TreeNode* root)
    {
        if (!root)
            return;
        
        inorderTraverse(root->left);
        vals.push_back(root->val);
        treeNodes.push_back(root);
        inorderTraverse(root->right);        
    }
private:
    vector<int> vals;  
    vector<TreeNode*> treeNodes;  
};
Better Solution: Constant space
class Solution {
public:
    void recoverTree(TreeNode *root) {
        TreeNode *n1=NULL;
        TreeNode *n2=NULL;
        TreeNode *prev=NULL;
        findTwoNodes(root,n1,n2,prev);
        
        if(n1!=NULL && n2!=NULL)
        {
            int tmp=n2->val;
            n2->val=n1->val;
            n1->val=tmp;
        }
    }
    void findTwoNodes(TreeNode *root, TreeNode *&n1, TreeNode *&n2, TreeNode *&prev)
    {
        if(root==NULL) return;
        
        findTwoNodes(root->left,n1,n2,prev);
        if(prev!=NULL && prev->val > root->val)
        {
            n2=root;
            if(n1==NULL)
            {
                n1=prev;
            }
        }
        prev=root;
        findTwoNodes(root->right,n1,n2,prev);
    }
};


联系
我们