Algorithm

LeetCode/Recover Binary Search Tree

Problem Summary

Two elements of a binary search tree are swapped. Recover the tree by swapping them again.

Solution 1

We can get the inorder traversal of the tree, and then the two nodes needed are easy to find. The time and space complexities are both O(N).

Solution 2

Suppose the two swapped nodes are i and j, their values being vi and vj (vi > vj). Then there are two possible situations:

  1. i and j are adjacent in the inorder traversal of the tree.

  2. Otherwise, there would be two nodes x and y, whose values being vx and vy, such that x is the successor of i in the inorder traversal, and y is the predecessor of j.

To find i and j, we use inorder traversal.
We can use two pointers p and q to remember the pointers to i and j, and a pointer pre to remember the predecessor of the current node. During the traversal, if we find that pre->val > cur->val, then we check p. If p has not been assigned with any value, we let p = pre and q = cur; else, we only let q = cur.
After the search, we switch the two nodes that p and q point to.

The time complexity of this method is also O(N), but the space it requires is only O(1).

Code for Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * 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 {
public:
    TreeNode *p = NULL, *q = NULL, *pre = NULL;
    void recoverTree(TreeNode* root) {
    	if (root == NULL)
    		return;
    	dfs(root);
    	if (p && q)
    	{
    		int tmp = p->val;
    		p->val = q->val;
    		q->val = tmp;
    	}
    }
    void dfs(TreeNode *root)
    {
    	if (root == NULL)
    		return;
    	dfs(root->left);
    	if (pre != NULL && root->val < pre->val)
    	{
    		if (p == NULL)
    		{
    			p = pre;
    			q = root;
    		}
    		else
    			q = root;
    	}
    	pre = root;
    	dfs(root->right);
    }
};