Task

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Example

  • Example 1:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

Input: [1,3,null,null,2]

   1
  /
 3
  \
   2

Output: [3,1,null,null,2]

   3
  /
 1
  \
   2
  • Example 2:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

Input: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

Output: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

Follow up:

A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

Solution

  • 考虑大小关系，使用中序遍历
  • 中序遍历的节点按照升序排列，故可认为是遍历已排好序的链表，找出被误交换的两个节点，如下图 leetcode99
  • 每次root指向一个节点，prev指向上次看到的节点
  • 异常发生时：prev的值大于root的值（违反升序）
    • 第一次异常发生时（第一个红框），prev是被误交换的节点
    • 第二次异常发生时（第二个红框），root是被误交换的节点
    • 用两个指针first和second分别指向这两个节点
  • 时间复杂度：遍历一次，O(n)
  • 空间复杂度：递归实现中序遍历，取决于递归深度，O(logn)-O(n)之间
  • 实现：
 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

// Runtime: 28 ms, faster than 89.65% of C++ online submissions for Recover Binary Search Tree.
// Memory Usage: 53.4 MB, less than 5.26% of C++ online submissions for Recover Binary Search Tree.
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void recoverTree(TreeNode* root) {
        inorder(root);
        //找到两个节点后交换它们的值
        swap(first->val,second->val);
    }
private:
    void inorder(TreeNode *root){
        if(!root) return;
        inorder(root->left);
        //中序遍历，在遍历左子树和右子树之间操作
        //判断异常发生
        if(prev && (prev->val > root->val)){
            //第一次发生异常时prev是被误交换的值
            if(!first) first=prev;
            //第二次发生异常时root是被交换的值
            second=root;
        }
        //更新prev
        prev=root;
        inorder(root->right);
    }
    TreeNode *first,*second,*prev=nullptr;
};