Sharing my 48ms C++ solution


  • 2
    T
    /**
     * 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 {
    private:
        void swap(TreeNode* &p1, TreeNode* &p2)
        {
            int temp = p1->val;
            p1->val = p2->val;
            p2->val = temp;
        }
        
        void recoverTreeFindTwoNodes(TreeNode* root, TreeNode* &prev, TreeNode* &first, TreeNode* &second)
        {
            if(root == NULL)
                return;
            recoverTreeFindTwoNodes(root->left, prev, first, second);
            if(prev && prev->val > root->val)
            {
                if(first)
                    second = root;
                else
                {
                    first = prev;
                    second = root;
                }
            }
            prev = root;
            recoverTreeFindTwoNodes(root->right, prev, first, second);
        }
    public:
        void recoverTree(TreeNode* root) {
            TreeNode* prev = NULL;
            TreeNode* first = NULL;
            TreeNode* second = NULL;
            recoverTreeFindTwoNodes(root, prev, first, second);
            if(first && second)
                swap(first, second);
        }
    };

  • 0
    T

    wow,same idea with you


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.