[LeetCode] Recover the tree without changing its structure.

Problem: You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.

Example:

Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.

Input: root = [3,1,4,null,null,2]
Output: [2,1,4,null,null,3]
Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.

Approach: Use inorder traversal to detect nodes to be swapped.

Implementation in C#:

    public void RecoverTree(TreeNode root) 

    {

        if (root == null)

        {

            return;

        }

        TreeNode first = null, second = null, prev = null;

        this.RecoverTreeFindNodes(root, ref first, ref second, ref prev);

        int temp = first.val;

        first.val = second.val;

        second.val = temp;

    }

    

    private void RecoverTreeFindNodes(TreeNode node, ref TreeNode first, ref TreeNode second, ref TreeNode prev)

    {

        if (node != null)

        {

            this.RecoverTreeFindNodes(node.left, ref first, ref second, ref prev);

            

            if (prev != null && node.val <= prev.val)

            {

                if (first == null)

                {

                    first = prev;

                }

                second = node;

            }

            prev = node;

            this.RecoverTreeFindNodes(node.right, ref first, ref second, ref prev);

        }

    }

Complexity: O(n)