[LeetCode] 99. Recover Binary Search Tree

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

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

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

恢复二叉搜索树。

题目即是题意。给的条件是一个不完美的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 题目总结