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

Recover the tree without changing its structure.

Example 1:

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

   1
  /
 3
  \
   2

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

   3
  /
 1
  \
   2

Example 2:

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?

恢复二叉搜索树。

题目即是题意。给的条件是一个不完美的BST，其中有两个节点的位置摆放反了，请将这个BST恢复。

这个题的思路其实很简单，就是中序遍历。followup不需要额外空间的做法我暂时不会做，日后再补充。既然是BST，中序遍历最管用了。中序遍历BST，正常情况是返回一个升序的数组，所以遍历过程中的相邻节点应该也是递增的。如果找到某个节点B小于等于他之前遍历到的那个节点A，则证明AB是那两个有问题的节点。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public void recoverTree(TreeNode root) {
 3         TreeNode pre = null;
 4         TreeNode cur = root;
 5         TreeNode first = null;
 6         TreeNode second = null;
 7         Stack<TreeNode> stack = new Stack<>();
 8         while (!stack.isEmpty() || cur != null) {
 9             while (cur != null) {
10                 stack.push(cur);
11                 cur = cur.left;
12             }
13             cur = stack.pop();
14             if (pre != null && cur.val <= pre.val) {
15                 if (first == null) {
16                     first = pre;
17                 }
18                 second = cur;
19             }
20             pre = cur;
21             cur = cur.right;
22         }
23         int temp = first.val;
24         first.val = second.val;
25         second.val = temp;
26     }
27 }

 

LeetCode 题目总结