Posts Tagged ‘BST’
这题看似很难，因为树的rotation完全不会；但是咬牙想了五分钟就bug free的写出来了，一遍过，看来树的recursive理解已经挺到位了。
算法：1～n中每个数字都可以是root，定了谁是root之后（比如k），他的左子树只能是1～k-1组成的，右子树只能是k+1～n组成的。左子树的variation数目×右子树的就是k作为root的有几种rotation。有点要注意：终止条件有两种：
- p == q，说明就一个节点了，没啥可转的，就一种return 1
- 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;
}
- In: 面经
- Leave a Comment
对这类题型其实不够熟悉，写了有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);
}
- 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:
Lexi's Leetcode solutions 