w**z
发帖数: 8232 | 1 我给个题吧。最近面试碰到的
Find number of subtrees in a tree which all nodes have the same value.
public int FindNumberOfSubTreesWithSameValue(Node root)
Note:
The leaf node itself is a subtree.
5
1 2
1 3
1
answer is 4 |
H***e
发帖数: 476 | 2 bottom up,
each subtree传true/false 给parent ,如果都为true
则比较left/right值是不是跟自己一样， 然后都相同就传true上去。 (同时update
number总数).
【在 w**z 的大作中提到】
: 我给个题吧。最近面试碰到的
: Find number of subtrees in a tree which all nodes have the same value.
: public int FindNumberOfSubTreesWithSameValue(Node root)
: Note:
: The leaf node itself is a subtree.
: 5
: 1 2
: 1 3
: 1
: answer is 4
|
C***U
发帖数: 2406 | 3 如果能把返回值改一下的话 可以用recursion做
【在 w**z 的大作中提到】
: 我给个题吧。最近面试碰到的
: Find number of subtrees in a tree which all nodes have the same value.
: public int FindNumberOfSubTreesWithSameValue(Node root)
: Note:
: The leaf node itself is a subtree.
: 5
: 1 2
: 1 3
: 1
: answer is 4
|
C***U
发帖数: 2406 | 4 我也是这么想 但是他的返回值只有int
【在 H***e 的大作中提到】
: bottom up,
: each subtree传true/false 给parent ,如果都为true
: 则比较left/right值是不是跟自己一样， 然后都相同就传true上去。 (同时update
: number总数).
|
p*****2
发帖数: 21240 | 5 如果左右subtree都是的话，并且左右和root相等的话加1就可以了吧？ |
p*****2
发帖数: 21240 | 6
wrap一下
【在 C***U 的大作中提到】
: 我也是这么想 但是他的返回值只有int
|
