[leetcode] Recover Binary Search Tree | BST有两个元素换位置了，不用额外空间的把他们换回来。

Posted by: lexigrey on: August 10, 2013

• In: leetcode
• 2 Comments

思路很straight forward，就是找到两个不属于自己位置的node，把他们的值互换。

但是怎么找这两个node就非常麻烦。怎么看出一个节点出位了？比如下图，能看出来是6出位了，但是1->6是满足的，6->3才发现不对劲。但也不能说prev > next就是prev不对，比如右边的5, 2，明明是2不对，但是2这个时候是后一个。所以总结来看，应该是“第一个不对劲的prev, curr pair是prev的错（不该跑前面的跑前面去了），第二个不对劲的prev, curr pair是curr的错（不该放后面的被放在了后面）。” 这个比较难想，总之就是中序遍历一遍，keep prev指针，按照刚说的规律找出那两个不对的。

       5
      /  \
     3     8
    / \   / \
   6   4 2   9
  /
 1

但是！！跑一遍不对！然后发现又是java不能改argument pointer的问题！栽在这上面两次了！！这回一定要弄清楚，记住教训！下面是错误版本：

private void populateMistakesArray(TreeNode[] mistakes, TreeNode root, TreeNode prev) {
  if (root == null)
    return;
  populateMistakesArray(mistakes, root.left, prev);
  if (prev != null && prev.val > root.val) {
    if (mistakes[0] == null)
      mistakes[0] = prev;
    mistakes[1] = root;
  }
  prev = root;
  populateMistakesArray(mistakes, root.right, prev);
}

这样传prev进来，prev = root这一句，method 里面叫prev的variable point to root了，然后传给下一层没问题，但是没法传给上一层！因为毕竟改的是local var， 上一层prev还是以前那个prev！！以前一直这么写树的题都没问题，是因为parameter要么一路往下传，要么想往上传的话就作为return object往上传。这次坑爹的，想往上传还放paramter里，必须挂。解决方法：用一个array把prev包起来(TreeNode[] preWrapper)，就能真的改para的内容了(prevWrapper[0] = root)

keep in order traversal pointer是个固定trick，见https://leetcodenotes.wordpress.com/2013/08/28/phone-%E6%A0%91populate-%E6%AF%8F%E4%B8%AA%E8%8A%82%E7%82%B9%E7%9A%84successor-pointer/

————————————————-10月份重做——————————————————

这个题第二遍做，又栽在一个trick里——如果swap的两个数正好在中序里面连着，那只能detect出来一次Out of order（比如1235467，发现5>4，然后mistake[0]放上5了，然后4<6，正常一路下去，mistake[1]永远也没被populate出来）。为了接住这个情况，在发现mistake[0]之后立刻把下一个当作mistake[1]赋上，要是后面真有mistake[1]，反正也会覆盖；要是后面没有，正好接住了上面说的特殊情况）。

Tree的test case:

 

Tags: BST, hard, tree, 固定解法, 中序