99. 恢复二叉搜索树

问题99 恢复二叉搜索树

https://leetcode-cn.com/problems/recover-binary-search-tree/

根据题目要求，一颗二叉搜索树，有两个节点的位置被对调了，现在需要恢复到对调前的状态，使它变为有效的二叉搜索树。首先这里不需要纠结于操作树指针，只需要定位到两个被对调的节点，然后交换它们的值就可以了。那么如何定位到两个被对调的节点呢？还得从二叉搜索树的定义入手。我们知道，一个二叉搜索树的中序遍历是一个递增序列，对调两个节点，等效于在一个递增序列中对调两个元素，根据前后元素的大小关系，我们是可以很方便地定位到这两个元素的。

这个题目和问题98是比较相似的，都是以二叉搜索树的中序遍历来做文章。

至于题目中空间复杂度O(1)的要求，瞅了眼下官方题解，额，有时间再研究下这个Morris中序遍历。

	public void recoverTree(TreeNode root) {
		List<TreeNode> inOrderList = new ArrayList<>();

		inOrderTraverse(root, inOrderList);

		TreeNode swappedLarge = null, swappedSmall = null;
		for (int i = 0; i < inOrderList.size() - 1; i++) {
			TreeNode cur = inOrderList.get(i);
			TreeNode next = inOrderList.get(i+1);
			if (cur.val > next.val) {
				swappedLarge = cur;
				break;
			}
		}
		for (int i = inOrderList.size() - 1; i > 0; i--) {
			TreeNode cur = inOrderList.get(i);
			TreeNode prev = inOrderList.get(i-1);
			if (cur.val < prev.val) {
				swappedSmall = cur;
				break;
			}
		}

		assert swappedLarge != null;
		assert swappedSmall != null;

		int tmp = swappedLarge.val;
		swappedLarge.val = swappedSmall.val;
		swappedSmall.val = tmp;
	}

	private void inOrderTraverse(TreeNode node, List<TreeNode> inOrderList) {
		if (node == null) {
			return;
		}

		inOrderTraverse(node.left, inOrderList);
		inOrderList.add(node);
		inOrderTraverse(node.right, inOrderList);
	}

在 LeetCode 查看