Lexi's Leetcode solutions

Posts Tagged ‘中序

思路:

  1. 因为没有random access,所以用in order的方式,一个一个遍历element,然后assign给parent
  2. 平时正常array convert bst都是用pre order的方式,root算好,然后left=.., right =…
  3. 一般你做树的bottom up是post order,left做出来,right做出来,root取决于这两个值
  4. 这里为什么要in order呢? 左,中,右的方式,正好是sorted。所以每次做完子树,然后下一个节点就是下一个位置。但是什么时候是个头呢,因为h.next会一直存在的,但是你的子树怎么知道什么时候返回到上一层?所以就要用p, q两个指针了,p代表当前sub list的头,q是尾。但是不要真的用他们来random access,就是用来stop就行了。
public TreeNode sortedListToBST(ListNode head) {
    int len = 0;
    ListNode dummy = head;
    while (dummy != null) {
       len++;
    dummy = dummy.next;
    }
    ListNode[] curr = new ListNode[1];
    curr[0] = head;
    return convert(curr, 0, len - 1);
}
private TreeNode convert(ListNode[] curr, int p, int q) {
    if (p > q)
        return null;
    int mid = (p + q) / 2;
    TreeNode left = convert(curr, p, mid - 1);
    TreeNode root = new TreeNode(curr[0].val);
    curr[0] = curr[0].next;
    TreeNode right = convert(curr, mid + 1, q);
    root.left = left;
    root.right = right;
    return root;
}
Advertisements
Tags: , , ,

别用傻乎乎的additional data structure,那样可以做,但是写起来太长。这个题上来的思路就是用左中右的inorder,这样一路下来,prev.next = curr,不断update当前的node为prev。但是写了半天,不知道怎么传prev,因为担心传java reference的问题;又回到了那个IntWrapper tree serialization的题。都是一个类型:https://leetcodenotes.wordpress.com/2013/08/24/phone-serializede-serialize-a-tree/

public void addSuccessor(Node node, Node[] prev) {
  if (node == null)
    return;
  addSuccessor(node.left, prev);
  if (prev[0] != null)
    prev[0].next = node;
  prev[0] = node;
  addSuccessor(node.right, prev);
}

类似题:找tree的in order traversal第x个节点:keep一个current node的index counter,同样是inorder的pattern,到当前node的时候counter++。这个init的i应该是-1,因为第一次找到最左边的节点的时候,i先+1,然后和x比较。

public TreeNode getNthNode(TreeNode node, IntWrapper i, int x) {
  if (node == null)
    return null;
  TreeNode foundAtLeft = getNthNode(node.left, i, x);
  i.val++;
  if (i.val == x)
    return node;
  if (foundAtLeft != null)
    return foundAtLeft;
  return getNthNode(node.right, i, x);
}

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