狗店面，求BLESS - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

狗店面，求BLESS

狗店面，求BLESS# JobHunting - 待字闺中

w*y2013-01-03 08:01

1 楼

1.两颗二叉树，但是一个节点可能有多个PARENT,判断是否相同。哎，STRUGGLE了很久
，最后写出来了，也不知道对不对。就是INORDER TRAVERSE的改一改
Example:
1
/ \
/ \
2 3
and
1
/ \
/ \
2 3
are identical. But
1
/ \
/ \
2 2
and
1
/ \
\ /
2
are NOT identical.
Also
1
/ \
/ \
2 \
/ \ /
/ \ /
2 2
\
\
2
and
1
/ \
/ \
2 \
/ \ \
/ \ \
2 2 /
\ /
\ /
2
are not identical.
第二面，LOCAL MINIMUM, 老题，早上刚练，不过问我PROOF问了半天，然后是EXTEND到
N*N的ARRAY的LOCAL MINIMUM的算法，给了提示以后相处算法了，不过没时间实现，问
了复杂度。
求BLESS啊。

w*y2013-01-03 08:01

2 楼

我不知道第一题对不对,谁能给个答案?

z*e2013-01-03 08:01

3 楼

some thoughts about the first question:
recursively determine if the left substree and right subtree is the same.
Also to avoid the recursive call on the same node multiple times, use the
hash table to store the visited node.
What is the exact question for the second one?

t*h2013-01-03 08:01

4 楼

seems it a node has multiple parents and there will be a cycle. compare the
cycles

【在 w*******y 的大作中提到】

: 1.两颗二叉树，但是一个节点可能有多个PARENT,判断是否相同。哎，STRUGGLE了很久
: ，最后写出来了，也不知道对不对。就是INORDER TRAVERSE的改一改
: Example:
: 1
: / \
: / \
: 2 3
: and
: 1
: / \

f*e2013-01-03 08:01

5 楼

第一题笨办法：一个map，两个sets--visited1,visitied2可以搞定。每遇到一个元素n
1 in tree1,n2 in tree2，判断visited1(n1)，visited2(n2)是否相等，如果相等并且为
true，看是否map(n1)=n2。如果都为false，把n1,n2加入visited1,visited2，map(n1)
=n2。
第二题用divide and conquer，先找出border(宽度为2,1也可以)上的最小元素m1，然后
在中心画个十字条，宽度为2，找出这个十字条上的最小元素m2，两步合起来就是一个
田字；如果m1<=m2，就在m1所在的那个小田里继续找，如果m1>m2，就在m2所在的那个小
田里继续找。

【在 w*******y 的大作中提到】

k*r2013-01-03 08:01

6 楼

mark

p*c2013-01-03 08:01

7 楼

Bless.
For the first problem, maybe it's sufficient to just cache the parent node
as we recursively traverse the two trees. At each node, we also compare the
cached parent nodes. So when we revisit a node for the second or third time,
the cached parent should be the same. I *think* this should work even if a
node has three, four or more parents.

e*e2013-01-03 08:01

8 楼

class TreeNode {
TreeNode left;
TreeNode right;
int parentCount;
}
private boolean isSame(TreeNode n1, TreeNode n2) {
if ( n1 == null && n2 == null )
return true;
if ( n1 == null || n2 == null )
return false;
return ++n1.parentCount == ++n2.parentCount && n1.val == n2.val &&
isSame( n1.left, n2.left ) && isSame( n1.right, n2.right );
}

o*d2013-01-03 08:01

9 楼

looks work to me. tks

【在 e****e 的大作中提到】

: class TreeNode {
: TreeNode left;
: TreeNode right;
: int parentCount;
: }
: private boolean isSame(TreeNode n1, TreeNode n2) {
: if ( n1 == null && n2 == null )
: return true;
: if ( n1 == null || n2 == null )
: return false;

g*r2013-01-03 08:01

10 楼

如果能改动两个树的话就 value +1

e*e2013-01-03 08:01

11 楼

Code for 不改动树。用一个Map记录每个node有多少parents.
Map map = new HashMap();
boolean isSame(TreeNode n1, TreeNode n2) {
if ( n1 == null && n2 == null )
return true;
if ( n1 == null || n2 == null )
return false;
setMap( n1 );
setMap( n2 );
return map.get(n1) == map.get(n2) && n1.val == n2.val && isSame( n1.left
, n2.left ) && isSame( n1.right, n2.right );
}
void setMap(TreeNode n) {
if ( map.containsKey( n ) )
map.put( n, map.get( n )++ );
else
map.put( n, 1 );
}

w*y2013-01-03 08:01

12 楼

parent counts are not unique for each node.
look at this example
Also
0
/ \
/ \
1 \
/ \ \
/ \ \
2 \ \
/ \ / \
/ \ / \
2 2 \
\ /
\ /
2 _ _ _ /
and
0
/ \
1 |
/ \ |
/ \|
2 \|
/ \ | \
/ \ _| \
2 2__/ /
\ /
\ /
2
are not identical

o*d2013-01-03 08:01

13 楼

ft, then, doesn't work

【在 w*******y 的大作中提到】

: parent counts are not unique for each node.
: look at this example
: Also
: 0
: / \
: / \
: 1 \
: / \ \
: / \ \
: 2 \ \

f*e2013-01-03 08:01

14 楼

今天凌晨3:00的时候想到了，刚想来爆料，结果被别人先爆了。
不过用标号就好了，不用parent count。保持一个全局变量，给节点依次标号，
当再次访问的时候标号不一样就不同。每个节点构造函数初始化标号为-1。
访问时标号为1至N。

【在 o***d 的大作中提到】

: ft, then, doesn't work

c*n2013-01-03 08:01

15 楼

bless

w*y2013-01-03 08:01

16 楼

素n
且为
n1)
然后
个小

【在 f*****e 的大作中提到】

: 第一题笨办法：一个map，两个sets--visited1,visitied2可以搞定。每遇到一个元素n
: 1 in tree1,n2 in tree2，判断visited1(n1)，visited2(n2)是否相等，如果相等并且为
: true，看是否map(n1)=n2。如果都为false，把n1,n2加入visited1,visited2，map(n1)
: =n2。
: 第二题用divide and conquer，先找出border(宽度为2,1也可以)上的最小元素m1，然后
: 在中心画个十字条，宽度为2，找出这个十字条上的最小元素m2，两步合起来就是一个
: 田字；如果m1<=m2，就在m1所在的那个小田里继续找，如果m1>m2，就在m2所在的那个小
: 田里继续找。

e*e2013-01-03 08:01

17 楼

Bless Louzhu.
Instead of using parentCount, use a map to record its parents. The code
might not be optimal, but it should work.
class TreeNode {
TreeNode left;
TreeNode right;
Map parentCount = new HashMap();
}
private boolean isSame(TreeNode n1, TreeNode n2, TreeNode p1, TreeNode p2) {
if ( n1 == null && n2 == null )
return true;
if ( n1 == null || n2 == null )
return false;

addParent( n1, p1 );
addParent( n2, p2 );
return hasSameParents( n1, n2 ) && n1.val == n2.val && isSame( n1.left,
n1, n2.left, n2 ) && isSame( n1.right, n1, n2.right, n2 );
}
private void addParent(TreeNode n, TreeNode p) {
Map pc = n.parentCount;
if ( pc.containsKey( p ) )
pc.put( p, pc.get( p )++ );
else
pc.put( p, 1 );
}
private boolean hasSameParents(TreeNode n1, TreeNode n2) {
Map pc1 = n1.parentCount;
Map pc2 = n2.parentCount;

if ( pc1.size() != pc2.size() )
return false;

for ( Entry e1 : parentCount1.entrySet() ) {
if ( !pc2.containsKey( e1.getKey() )
return false;
else if ( e1.getValue() != pc2.get( e1.getKey() ) ) {
return false;
}
}
return true;
}

f*e2013-01-03 08:01

18 楼

把parent count用序号代替就行了，都是integer，你前面的代码基本不变。不用
你现在这么复杂的。
http://mitbbs.com/article1/JobHunting/32295883_3_0.html

{

【在 e****e 的大作中提到】

: Bless Louzhu.
: Instead of using parentCount, use a map to record its parents. The code
: might not be optimal, but it should work.
: class TreeNode {
: TreeNode left;
: TreeNode right;
: Map parentCount = new HashMap();
: }
: private boolean isSame(TreeNode n1, TreeNode n2, TreeNode p1, TreeNode p2) {
: if ( n1 == null && n2 == null )

w*y2013-01-03 08:01

19 楼

我给的SOLUTION就这样。

【在 f*****e 的大作中提到】

: 今天凌晨3:00的时候想到了，刚想来爆料，结果被别人先爆了。
: 不过用标号就好了，不用parent count。保持一个全局变量，给节点依次标号，
: 当再次访问的时候标号不一样就不同。每个节点构造函数初始化标号为-1。
: 访问时标号为1至N。

e*e2013-01-03 08:01

20 楼

Gotcha. Thank you for letting me know this simple solution.

【在 f*****e 的大作中提到】

: 把parent count用序号代替就行了，都是integer，你前面的代码基本不变。不用
: 你现在这么复杂的。
: http://mitbbs.com/article1/JobHunting/32295883_3_0.html
:
: {

w*y2013-01-03 08:01

21 楼

{
感觉通不过第二个例子。

【在 e****e 的大作中提到】

e*e2013-01-03 08:01

22 楼

Here is the code for the 序号标记 approach. It's surprisingly simple. Thanks
fatalme for posting it out. Sorry for my rusty C/C++.
class TreeNode {
TreeNode left;
TreeNode right;
int no = -1;
}
Initialize: n1.no = 1; n2.no = 1; No = 1;
bool isSame(TreeNode n1, TreeNode n2, int& NO) {
if ( !n1 && !n2 )
return true;
if ( !n1 || !n2 )
return false;
if ( n1.no != n2.no || n1.val != n2.val )
rturn false;

NO++;
n1.left.no = NO;
n2.left.no = NO;
if ( !isSame( n1.left, n2.left, NO ) )
return false;

NO++;
n1.right.no = NO;
n2.right.no = NO;
return isSame( n1.right, n2.right );
}

【在 f*****e 的大作中提到】

: 把parent count用序号代替就行了，都是integer，你前面的代码基本不变。不用
: 你现在这么复杂的。
: http://mitbbs.com/article1/JobHunting/32295883_3_0.html
:
: {

c*22013-01-03 08:01

23 楼

第一题这样做可以吗？
做pre-order traversal，如果两个node相同比较parent list是否相同。
然后递归看左右子树是否相同。
public class TreeNode {
TreeNode left;
TreeNode right;
int val;
ArrayList parents = new ArrayList();
public TreeNode(int val) {this.val = val;}
}
public boolean isIdentical(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) return true;
if (t1 == null && t2 != null) return false;
if (t1 != null && t2 == null) return false;
if (t1.val != t2.val) return false;
if (!hasSameParents(t1, t2)) return false;
return isIdentical(t1.left, t2.left) && isIdentical(t1.right, t2.right);
}
public boolean hasSameParents(TreeNode t1, TreeNode t2) {
if (t1.parents.size() != t2.parents.size()) return false;
for (int i = 0; i < parents.size(); i++) {
if (t1.parents.get(i) != t2.parents.get(i) return false;
}
return true;
}

c*22013-01-03 08:01

24 楼

Thanks
不能简单的只算number of parent吧，如果一个node有相同的parent数但实际指向不同
的parent呢？

【在 e****e 的大作中提到】

: Here is the code for the 序号标记 approach. It's surprisingly simple. Thanks
: fatalme for posting it out. Sorry for my rusty C/C++.
: class TreeNode {
: TreeNode left;
: TreeNode right;
: int no = -1;
: }
: Initialize: n1.no = 1; n2.no = 1; No = 1;
: bool isSame(TreeNode n1, TreeNode n2, int& NO) {
: if ( !n1 && !n2 )

c*22013-01-03 08:01

25 楼

第二题能不能具体把题目贴一下啊？好像听说过，但不知道具体是哪题。

e*e2013-01-03 08:01

26 楼

You're absolutely right. I wrote some new code based on 序号标记. Please
take a look at my last post.

【在 c*****2 的大作中提到】

: 第二题能不能具体把题目贴一下啊？好像听说过，但不知道具体是哪题。

w*y2013-01-03 08:01

27 楼

看来给的SOLUTION是对的。听天由命了。。。

e*e2013-01-03 08:01

28 楼

Bless. Can you 详细说说 the second question's 题目要求？ Thanks.

【在 w*******y 的大作中提到】

: 看来给的SOLUTION是对的。听天由命了。。。

w*y2013-01-03 08:01

29 楼

find local minimum
如果一个数组里的成员 a[i]] LOCAL MINIMUM就可以。
extend到在n*n的MATRIX上如何找LOCAL MINIMUM.

【在 e****e 的大作中提到】

: Bless. Can you 详细说说 the second question's 题目要求？ Thanks.

e*e2013-01-03 08:01

30 楼

Thank you so much. 网上我见到local mim还有个条件a[0] >= a[1] and a[n-1] <= a
[n]，没有这个条件题目没法用二分法做吧！

[0

【在 w*******y 的大作中提到】

:
: find local minimum
: 如果一个数组里的成员 a[i]: ] : LOCAL MINIMUM就可以。
: extend到在n*n的MATRIX上如何找LOCAL MINIMUM.

l*a2013-01-03 08:01

31 楼

2d情况下的local minimum有几个neighbour，4个还是8个？
ps：从其他g家店面的水看到了lz店面的真金白银啊。

[0

【在 w*******y 的大作中提到】

:
: find local minimum
: 如果一个数组里的成员 a[i]: ] : LOCAL MINIMUM就可以。
: extend到在n*n的MATRIX上如何找LOCAL MINIMUM.

m*k2013-01-03 08:01

32 楼

只要能想个办法，用一个字符串唯一地表示这棵树，就可以通过比较两棵树的字符串是
否相等来得到答案。
显然这道题是要判断树的结构是否相等，跟结点上的value无关（如果也要求value，下
面的方法也work）。
假设树的结点无value，随便用一种方式给一棵树的每个结点编号（用visited/un-
visited, DFS/BFS皆可）。然后求出每个结点所有的父节点，用BFS可以实现。假设结
点i的所有父节点为a,b,c (a然后对树进行分层表示，假设树为：
1
/ \
2 3
/ \ \
4 5 6
则字符串为：
[Node1][Node2_Node3][Node4_Node5_Node6]
然后把其中每个Nodei以Node(i|a,b,c)代替，最后得到的字符串就是这棵树的表示串（
即用这个串可以唯一地还原这颗树的结构）。
最后比较两棵树的表示串是否相等即可。

【在 w*******y 的大作中提到】

w*y2013-01-03 08:01

33 楼

四个neighbours.

【在 l*****a 的大作中提到】

: 2d情况下的local minimum有几个neighbour，4个还是8个？
: ps：从其他g家店面的水看到了lz店面的真金白银啊。
:
: [0

p*p2013-01-03 08:01

34 楼

big big bless!

f*t2013-01-03 08:01

35 楼

层序遍历+hashmap解法。动手写+test大概25分钟
public static boolean compareTrees(TreeNode tree1, TreeNode tree2) {
if (tree1 == null && tree2 == null)
return true;
else if (tree1 == null || tree2 == null)
return false;
HashMap map = new HashMap();
LinkedList list1 = new LinkedList();
LinkedList list2 = new LinkedList();
list1.add(tree1);
list2.add(tree2);

int count = 1;
while (count > 0) {
for (int i = 0; i < count; i++) {
TreeNode n1 = list1.get(0);
TreeNode n2 = list2.get(0);
list1.removeFirst();
list2.removeFirst();
TreeNode target = map.get(n1);
if (target == null) {
map.put(n1, n2);
} else if (n2 != target) {
return false;
}
if (n1.val != n2.val)
return false;
if ((n1.left == null && n2.left != null) || (n1.left != null
&& n2.left == null)) {
return false;
} else if (n1.left != null && n2.left != null) {
list1.add(n1.left);
list2.add(n2.left);
}
if ((n1.right == null && n2.right != null) || (n1.right !=
null && n2.right == null)) {
return false;
} else if (n1.right != null && n2.right != null) {
list1.add(n1.right);
list2.add(n2.right);
}
}
count = list1.size();
}

return true;
}

o*d2013-01-03 08:01

36 楼

大牛,我仔细重新看了一下第一题,不明白到底题意是什么,能再解释一下么?
我猜的Node:
//each node can have at most two parents
struct Node
{
Node* left;
Node* right;
Node* leftParent;
Node* rightParent;
};
//另一种
struct Node
{
Node* left;
Node* right;
vector parents;
};
问题1:================================================
从父亲到子节点是可以双向访问的?换句话说,如果一个子节点有一个父节点,那么从父
节点也可以访问到资节点?
如果是这样,我觉得单纯用parents就可以搞定这题,不需要加标号阿.你后面回帖的反例
里面,一个节点有3个父节点.那么你在查找这个子节点时,仍然能发现一个树的父节点有
3个,另一个只有两个阿.
我找不到反例。
//P-code
//return false if any check fails
isSame(node n1, node n2)
{
check(n1->val, n2->val);
check(n1->parents.size()==n2->parents.size());
for(i=1 to n1->parents.size())
check(n1->parents[i]->val,n2->parents[i]->val);
check(n1->left,n2->left);
check(n1->right,n2->right);
}
问题2:================================================
如果问题1的假设不成立，那么就是说父节点可以只访问某几个子节点而不是所有的子
节点？也就是说，某个子节点可以有无穷多个父节点？
好吧，如果这样，那就没办法了。

【在 w*******y 的大作中提到】

p*22013-01-03 08:01

37 楼

第一题就是DFS吧。有什么特别的吗？

o*d2013-01-03 08:01

38 楼

不行,你看他给的第三个例子,dfs w/o checking parents会给出两个树相同的结论,其
实不同.

【在 p*****2 的大作中提到】

: 第一题就是DFS吧。有什么特别的吗？

f*e2013-01-03 08:01

39 楼

前面的讨论已经讲得很清楚了，还问。

【在 o***d 的大作中提到】

: 不行,你看他给的第三个例子,dfs w/o checking parents会给出两个树相同的结论,其
: 实不同.

p*22013-01-03 08:01

40 楼

感觉可以很容易检查出来呀我miss什么了吗感觉这题就是检查两个graph是否相同吧

【在 o***d 的大作中提到】

: 不行,你看他给的第三个例子,dfs w/o checking parents会给出两个树相同的结论,其
: 实不同.

f*e2013-01-03 08:01

41 楼

node如果要你自己设计就O(N)，你设计的两个node，不能满足要求。如果只是left and
right就要用map,就是O(NlogN)

【在 o***d 的大作中提到】

: 大牛,我仔细重新看了一下第一题,不明白到底题意是什么,能再解释一下么?
: 我猜的Node:
: //each node can have at most two parents
: struct Node
: {
: Node* left;
: Node* right;
: Node* leftParent;
: Node* rightParent;
: };

f*e2013-01-03 08:01

42 楼

isomophism比这个难多了。

【在 p*****2 的大作中提到】

:
: 感觉可以很容易检查出来呀我miss什么了吗感觉这题就是检查两个graph是否相同吧

o*d2013-01-03 08:01

43 楼

我问的原因是,我发现当时worstdboy在12楼给的反例不能推翻用parent来检查的方法.
换句话说,我觉得用parent来查就够了,后来 "迪迪"改进的方法,我觉得没必要似乎.

【在 f*****e 的大作中提到】

: 前面的讨论已经讲得很清楚了，还问。

p*p2013-01-03 08:01

44 楼

所有点值不同是可以的，有相同的你没法保证那是同一个点

【在 p*****2 的大作中提到】

:
: 感觉可以很容易检查出来呀我miss什么了吗感觉这题就是检查两个graph是否相同吧

f*e2013-01-03 08:01

45 楼

parent用count(type int)，不能分辨。parent用你说的那种就变成O(NlgN)了。

【在 o***d 的大作中提到】

: 我问的原因是,我发现当时worstdboy在12楼给的反例不能推翻用parent来检查的方法.
: 换句话说,我觉得用parent来查就够了,后来 "迪迪"改进的方法,我觉得没必要似乎.

o*d2013-01-03 08:01

46 楼

问题是后来迪迪给出的解法也有bug吧?我觉得他还是应该再访问一下每个节点的parent
->NO,否则也不成.那样他的复杂度也一样啊

【在 f*****e 的大作中提到】

: parent用count(type int)，不能分辨。parent用你说的那种就变成O(NlgN)了。

o*d2013-01-03 08:01

47 楼

哦,sorry,我不知道你打算这么做,这么做应该没问题吧

【在 p*****2 的大作中提到】

:
: 感觉可以很容易检查出来呀我miss什么了吗感觉这题就是检查两个graph是否相同吧

o*d2013-01-03 08:01

48 楼

不过无所谓了,反正这道题大致的解法我也知道了,遇上应该没问题

parent

【在 o***d 的大作中提到】

: 问题是后来迪迪给出的解法也有bug吧?我觉得他还是应该再访问一下每个节点的parent
: ->NO,否则也不成.那样他的复杂度也一样啊

f*e2013-01-03 08:01

49 楼

加入leetcode就比较好。

【在 o***d 的大作中提到】

: 不过无所谓了,反正这道题大致的解法我也知道了,遇上应该没问题
:
: parent

p*22013-01-03 08:01

50 楼

也许我理解错了。我简单写了一个，看看有没有问题。
def check(left:TreeNode, right:TreeNode)={
def dfs(left:TreeNode, right:TreeNode):Boolean={
if(left==null || right==null) return left==right
if(map1.contains(left) || map2.contains(right)) return map1.
contains(left) && map1(left)==right && map2.contains(right) && map2(right)==
left
map1(left)=right
map2(right)=left
return left.value==right.value && dfs(left.left,right.left) &&
dfs(left.right,right.right)
}

val map1=Map[TreeNode,TreeNode]()
val map2=Map[TreeNode,TreeNode]()
dfs(left,right)
}

o*d2013-01-03 08:01

51 楼

我彻底理解错了?
大牛,你在哪里处理了parent的情况?
如果你这是写的graph dfs,那么你怎么处理一个node has three edges??
like this:
2
/ \
2 \
/ \ |
2 2 |
\ /
2

==

【在 p*****2 的大作中提到】

: 也许我理解错了。我简单写了一个，看看有没有问题。
: def check(left:TreeNode, right:TreeNode)={
: def dfs(left:TreeNode, right:TreeNode):Boolean={
: if(left==null || right==null) return left==right
: if(map1.contains(left) || map2.contains(right)) return map1.
: contains(left) && map1(left)==right && map2.contains(right) && map2(right)==
: left
: map1(left)=right
: map2(right)=left
: return left.value==right.value && dfs(left.left,right.left) &&

p*22013-01-03 08:01

52 楼

没明白为什么要处理parent？

【在 o***d 的大作中提到】

: 我彻底理解错了?
: 大牛,你在哪里处理了parent的情况?
: 如果你这是写的graph dfs,那么你怎么处理一个node has three edges??
: like this:
: 2
: / \
: 2 \
: / \ |
: 2 2 |
: \ /

o*d2013-01-03 08:01

53 楼

当然,二爷,你如果继续dfs,那么你可以再加上parent,然后再加上cycle的verification
,我相信肯定能work的

【在 o***d 的大作中提到】

p*22013-01-03 08:01

54 楼

verification
到底为什么要处理parent呀？

【在 o***d 的大作中提到】

: 当然,二爷,你如果继续dfs,那么你可以再加上parent,然后再加上cycle的verification
: ,我相信肯定能work的

o*d2013-01-03 08:01

55 楼

别吓我,我理解错误?
原文第三个例子,你确定你的code没问题?可以区分这两个tree different?
1
/ \
/ \
2 \
/ \ /
/ \ /
2 2
\
\
2
and
1
/ \
/ \
2 \
/ \ \
/ \ \
2 2 /
\ /
\ /
2
are not identical.

【在 p*****2 的大作中提到】

:
: verification
: 到底为什么要处理parent呀？

o*d2013-01-03 08:01

56 楼

我也懵了,算了,知道一种做法就可以了吧
我一直不清楚这题的准确要求是什么,比如node的定义

【在 o***d 的大作中提到】

: 别吓我,我理解错误?
: 原文第三个例子,你确定你的code没问题?可以区分这两个tree different?
: 1
: / \
: / \
: 2 \
: / \ /
: / \ /
: 2 2
: \

f*e2013-01-03 08:01

57 楼

只用map就行的，就是性能可能要差一些。

【在 o***d 的大作中提到】

: 别吓我,我理解错误?
: 原文第三个例子,你确定你的code没问题?可以区分这两个tree different?
: 1
: / \
: / \
: 2 \
: / \ /
: / \ /
: 2 2
: \

o*d2013-01-03 08:01

58 楼

二爷,我要做题去了,为了这么一题,花这么多时间不值,我还有很多题没做呢

【在 p*****2 的大作中提到】

:
: verification
: 到底为什么要处理parent呀？

p*22013-01-03 08:01

59 楼

感觉这个时候就能刊出来了吧？这个是有左孩子，那个是有右孩子
2 \
/ \ /

【在 o***d 的大作中提到】

: 别吓我,我理解错误?
: 原文第三个例子,你确定你的code没问题?可以区分这两个tree different?
: 1
: / \
: / \
: 2 \
: / \ /
: / \ /
: 2 2
: \

p*22013-01-03 08:01

60 楼

你的做法是什么呀？

【在 o***d 的大作中提到】

: 我也懵了,算了,知道一种做法就可以了吧
: 我一直不清楚这题的准确要求是什么,比如node的定义

o*d2013-01-03 08:01

61 楼

靠,我完全想错了....
真对不住....
你们的做法是对的.
这题的node结构就是
node
{left,right,val}

【在 p*****2 的大作中提到】

:
: 你的做法是什么呀？

p*p2013-01-03 08:01

62 楼

不明白……
那个例子里
树1：1 (root) - right connected to 2 (at depth 2)
树2：1 (root) - right connected to 2 (at depth 3)
两个2节点都是叶子节点，怎么看出来？

【在 p*****2 的大作中提到】

:
: 你的做法是什么呀？

P*b2013-01-03 08:01

63 楼

n*n怎么做？

[0

【在 w*******y 的大作中提到】

:
: 四个neighbours.

p*22013-01-03 08:01

64 楼

哪个例子？

【在 p*****p 的大作中提到】

: 不明白……
: 那个例子里
: 树1：1 (root) - right connected to 2 (at depth 2)
: 树2：1 (root) - right connected to 2 (at depth 3)
: 两个2节点都是叶子节点，怎么看出来？

p*22013-01-03 08:01

65 楼

一维不是有前提条件吗？二维的前提条件有吗？

【在 P*******b 的大作中提到】

: n*n怎么做？
:
: [0

w*p2013-01-03 08:01

66 楼

第一题，我会想按照图来做，类似BFS, 从root, 把所有的left, right Children放到
queue里。放后mark颜色，每次 add elements 到queue的时候，比较两个queue 加入的
element 和个数是不是一样。

【在 w*******y 的大作中提到】

w*p2013-01-03 08:01

67 楼

思路，code，简洁。赞。

【在 e****e 的大作中提到】

w*p2013-01-03 08:01

68 楼

这个提示的好。
把parent counts 改成，node 的height, 比较child的时候同时比较他们的height.

【在 w*******y 的大作中提到】

: parent counts are not unique for each node.
: look at this example
: Also
: 0
: / \
: / \
: 1 \
: / \ \
: / \ \
: 2 \ \

w*p2013-01-03 08:01

69 楼

一维的LOCAL MINIMUM, 就是先check下两头，然后从头scan 到尾，看有没有值比左右
小，考点在哪里？有更
好的思路嘛？
N*N的， MATRIX 从0，0开始。
int findMinArround ( Matrix m, point p) //把point p 所有的8个点扫一遍，找到
最小点。如果这个最小点min 比 p value 大，就返回p 的 value; 如果最小点小与p
的value, 就call findMinArround ( Matrix m, point min)
考点在哪里？有更好的思路嘛？不晓得，我的思路对不对。有人提到partition咋
整的？
worse case n^2.

[0

【在 w*******y 的大作中提到】

:
: 四个neighbours.

j*x2013-01-03 08:01

70 楼

还是peking2经验丰富，这题一眼看出了关键其实就是tree isomorohisim，树上的同
构而已

【在 o***d 的大作中提到】