Lexi's Leetcode solutions

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

Posted on: August 10, 2013

思路很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:

 

Advertisements

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

我用了一个ArrayList作为传参。ArrayList hold an object entry,那个object entry 可以用ArrayList.set(0,new obj entry)来修改,这样就可以传递了,不知道是不是可可以解决你想解决的问题。我在validate binary tree里用过了,可以work.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: