099 Recover Binary Search Tree
2019-02-20 本文已影响0人
烟雨醉尘缘
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Example：
Input: [1,3,null,null,2]
Output: [3,1,null,null,2]
Input: [3,1,4,null,null,2]
Output: [2,1,4,null,null,3]
Note：
A solution using O(n) space is pretty straight forward.
Could you devise a constant space solution?
解释下题目：
二叉搜索树里有两个节点被交换了，在保持树的结构下把这两个值换回来
1. 遍历找
实际耗时：26ms
private TreeNode firstElement = null;
private TreeNode secondElement = null;
private TreeNode prevElement = new TreeNode(Integer.MIN_VALUE);
public void recoverTree(TreeNode root) {
traverse(root);
int temp = firstElement.val;
firstElement.val = secondElement.val;
secondElement.val = temp;
}
private void traverse(TreeNode root) {
if (root == null)
return;
traverse(root.left);
//接下来是遍历中“应该打印的地方”
if (firstElement == null && prevElement.val >= root.val) {
firstElement = prevElement;
}
if (firstElement != null && prevElement.val >= root.val) {
secondElement = root;
}
prevElement = root;
//“打印结束”
traverse(root.right);
}
踩过的坑：只有两个数被交换了！！我一开始没看到！！！导致把问题极度复杂化了！！
思路：就是利用遍历的方法找到这两个违反二叉搜索树的数，然后交换就行了。
