My simple recursion solution using 61ms


  • 0
    F
    class Solution {
    public:
        void recoverTree(TreeNode* root) {
            TreeNode *node1 = NULL, *node2 = NULL, *prev = NULL;
            searchSwapped(root, node1, node2, prev);
            int val = node1->val;
            node1->val = node2->val;
            node2->val = val;
        }
    private:
        void searchSwapped(TreeNode *node, TreeNode *&node1, TreeNode *&node2, TreeNode *&prev) {
            if (NULL == node)   return;
            searchSwapped(node->left, node1, node2, prev);
            if (NULL!=prev && node->val<prev->val) {
                if (NULL == node1)  {
                    node1 = prev;
                }
                node2 = node;
            }
            prev = node;
            searchSwapped(node->right, node1, node2, prev);
        }
    };

Log in to reply
 

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