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 1:
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.
Example 2:
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.
Constraints:
The number of nodes in the tree is in the range [2, 1000].
-231 <= Node.val <= 231 - 1
Follow up: A solution using O(n) space is pretty straight-forward. Could you devise a constant O(1) space solution?
Solutions
Solution 1: In-order Traversal
In-order traversal of a binary search tree results in an increasing sequence. If two nodes' values are mistakenly swapped, there will definitely be two reverse pairs in the sequence obtained from the in-order traversal. We use first and second to record the smaller and larger values of these two reverse pairs, respectively. Finally, swapping the values of these two nodes will correct the mistake.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary search tree.
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcrecoverTree(root*TreeNode){varprev,first,second*TreeNodevardfsfunc(*TreeNode)dfs=func(root*TreeNode){ifroot==nil{return}dfs(root.Left)ifprev!=nil&&prev.Val>root.Val{iffirst==nil{first=prev}second=root}prev=rootdfs(root.Right)}dfs(root)first.Val,second.Val=second.Val,first.Val}