Lexi's Leetcode solutions

Posts Tagged ‘BST

这题看似很难,因为树的rotation完全不会;但是咬牙想了五分钟就bug free的写出来了,一遍过,看来树的recursive理解已经挺到位了。

算法:1~n中每个数字都可以是root,定了谁是root之后(比如k),他的左子树只能是1~k-1组成的,右子树只能是k+1~n组成的。左子树的variation数目×右子树的就是k作为root的有几种rotation。有点要注意:终止条件有两种:

  1. p == q,说明就一个节点了,没啥可转的,就一种return 1
  2. p > q,说明这一段已经不存在了,这时不应该return 0,因为这正是子树是null的情况!所以还应该return 1
public int numTrees(int n) {
  return getWays(1, n);
}
int getWays(int p, int q) {
  if (p >= q)
    return 1;
  int ways = 0;
  for (int i = p; i <= q; i++) {
    int leftWays = getWays(p, i - 1);
    int rightWays = getWays(i + 1, q);
    ways += leftWays * rightWays;
  }
  return ways;
}
Advertisements
Tags: , ,

对这类题型其实不够熟悉,写了有15分钟才出来,太差了。总结一下。

BST一般找不到就null了,没办法keep track of走到哪个位置的信息。所以多传两个参数,leftBoundary和rightBoundary,分别表示“当前node为root的子树的left boundary – 当前子树的immediate prev)“和“immediate next”。因为你是top down的往下算,所以左右两边的boundary不断narrow down。当node == null时,此时的最靠近自己的boundary就起作用了,找他们之间最接近x的就行了。

这题和判断一棵树是不是BST是一个套路(后面有对比):

public TreeNode getClosest(TreeNode node, TreeNode leftBoundary, TreeNode rightBoundary, int x) {
  if (node == null)
    return getClosest(leftBoundary, rightBoundary, x);
  if (node.val < x) {
    return getClosest(node.right, node, rightBoundary, x);
  } else {
    return getClosest(node.left, leftBoundary, node, x);
  }
}
private TreeNode getClosest(TreeNode prev, TreeNode next, int x) {
  if (prev == null || next == null)
    return prev == null ? next : prev;
  if (next.val - x < x - prev.val)
    return next;
  else
    return prev;
}

附加:判断一棵树是不是BST,也是一路传下来boundary,不断看当前节点是不是满足上面传下来的左右boundary, 然后往下传的时候narrow down。最开始left, right, node都是null(没有左右节点限制)。

boolean isBST(Node node, Node leftBoundary, Node rightBoundary) {
  if (node == null)
    return true;
  if ((leftBoundary != null && node.val < leftBoundary.val) || (rightBoundary != null && node.val > rightBoundary.val))
    return false;
  if (!isBST(node.left, leftBoundary, node))
    return is BST(node.right, node, rightBoundary);
}

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