d******i
发帖数: 76 | 1 谢谢@wwwyhx大牛贡献的题。看了帖子里面的回复后，有了些思路，虽然对于牛人们，
这道题很简单，对于还是菜鸟的我还是很难的，发个帖子，供大家讨论，希望最
终得出正确的答案吧。
“我面的时候有一简单题一定要O(n), 找树的unival个数(就是这个节点开始所有子树都
一样的节点数) ”
题的意思是，找到这样的子树，满足子树中所有节点的值相等。计算满足此条件的子树
中节点的总个数。（希望没有理解错。）
例子1：
1
结果为 1
例子2：
1
1 1
结果为 3
例子3：
1
2 3
结果为2（2, 3）
例子4：
1
2 3
2
结果为：3 ({2,2}, {3})
例子 5：
1
2 3
2
4
结果为： 2 （4，3）；
下面是C++代码，大家指正
---------------更新：不需要看我写的了，直接看楼下的解法吧，哈哈。-----------
----
#include
#include
using namespace std;
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int v) : val(v), left(NULL), right(NULL) {}
};
int findUnivalSubtrees(TreeNode *root, int &count)
{
if(root == NULL) return 0;
int left_c = findUnivalSubtrees(root->left, count);
int right_c = findUnivalSubtrees(root->right, count);
if(root->left && root->right && root->left->val == root->val && root->
right->val == root->val)
{
if(left_c * right_c == 0)//subtree have different values
return 0;
++count;
return left_c + right_c + 1;
}
else if(root->left && root->right == NULL &&root->left->val == root->val)
{
if(left_c == 0)//subtree have different values
return 0;
++count;
return left_c + 1;
}
else if( root->right && root->left == NULL && root->right->val == root->
val)
{
if(right_c == 0)//subtree have different values
return 0;
++count;
return right_c + 1;
}else if(root->left == NULL && root->right == NULL)
{
++count;;
return 1;
}
return 0;
} |
w****x
发帖数: 2483 | |
d******i
发帖数: 76 | 3
想了想，不知道怎么写的更加简洁，能否给点意见，谢谢了
【在 w****x 的大作中提到】
: 代码写成这样就挂了，我记得写的大概只有这得一半
|
p*****2
发帖数: 21240 | 4
int ans=0;
boolean dfs(Node root)
{
if(root==null)
return true;
boolean l=dfs(root.left);
boolean r=dfs(root.right);
if(l && r && (root.left==null || root.left.val==root.val) && (root.
right==null || root.right.val==root.val))
{
ans++;
return true;
}
return false;
}
【在 d******i 的大作中提到】
:
: 想了想，不知道怎么写的更加简洁，能否给点意见，谢谢了
|
l*********8
发帖数: 4642 | 5 那么他的题意描述的对的吧？
【在 w****x 的大作中提到】
: 代码写成这样就挂了，我记得写的大概只有这得一半
|
h****n
发帖数: 1093 | 6 写的太罗嗦了
你可以参考我在那个帖子里的代码
【在 d******i 的大作中提到】
:
: 想了想，不知道怎么写的更加简洁，能否给点意见，谢谢了
|
d******i
发帖数: 76 | 7
....无地自容了...
【在 p*****2 的大作中提到】
:
: int ans=0;
: boolean dfs(Node root)
: {
: if(root==null)
: return true;
: boolean l=dfs(root.left);
: boolean r=dfs(root.right);
: if(l && r && (root.left==null || root.left.val==root.val) && (root.
: right==null || root.right.val==root.val))
|
d******i
发帖数: 76 | 8
我这差距也太大了，哈哈，谢谢批评。
【在 w****x 的大作中提到】
: 代码写成这样就挂了，我记得写的大概只有这得一半
|
p*****2
发帖数: 21240 | 9
膜拜yhx，这题一遍写对好像也不容易。
【在 d******i 的大作中提到】
:
: 我这差距也太大了，哈哈，谢谢批评。
|
l*********8
发帖数: 4642 | 10 刚写了一个，发现跟二爷的很像啊，呵呵。
inline bool diffVar(Node* p, Node* q) { return p&&q && p->var != q->var;};
bool uniVar(Node * root, int & num)
{
if (!root)
return true;
if ( uniVar(root->left, num) && !diffVar(root, root->left)
&& uniVar(root->right,num) && !diffVar(root, root->right)) {
num++;
return true;
}
return false;
}
【在 p*****2 的大作中提到】
:
: 膜拜yhx，这题一遍写对好像也不容易。
|
|
|
p*****2
发帖数: 21240 | 11
测过吗？
【在 l*********8 的大作中提到】
: 刚写了一个，发现跟二爷的很像啊，呵呵。
: inline bool diffVar(Node* p, Node* q) { return p&&q && p->var != q->var;};
: bool uniVar(Node * root, int & num)
: {
: if (!root)
: return true;
: if ( uniVar(root->left, num) && !diffVar(root, root->left)
: && uniVar(root->right,num) && !diffVar(root, root->right)) {
: num++;
: return true;
|
l*********8
发帖数: 4642 | 12 只是目测过。。。。
【在 p*****2 的大作中提到】
:
: 测过吗？
|
p*****2
发帖数: 21240 | 13
会不会有bug？
【在 l*********8 的大作中提到】
: 只是目测过。。。。
|
l*********8
发帖数: 4642 | 14 恩， 我一开始就写错了。 错误代码如下：
inline bool diffVar(Node * p, Node* q) { return p&&q && p->var != q->var;};
bool uniVar(Node * root, int & num)
{
if (!root)
return true;
if ( !uniVar(root->left, num) || diffVar(root, root->left)
|| !uniVar(root->right,num) || diffVar(root, root->right)) {
return false;
}
num++;
return true;
}
【在 p*****2 的大作中提到】
:
: 会不会有bug？
|
l*********8
发帖数: 4642 | 15 你觉得什么地方有问题？
【在 p*****2 的大作中提到】
:
: 会不会有bug？
|
p*****2
发帖数: 21240 | 16
uniVar(root->left, num) && !diffVar(root, root->left)
&& uniVar(root->right,num) && !diffVar(root, root->right)
这句，如果uniVar returns false。会不会有问题？
【在 l*********8 的大作中提到】
: 你觉得什么地方有问题？
|
l*********8
发帖数: 4642 | 17 说的对！ 还是我之前错误代码犯得错误！ 在同一个地方摔倒了两次啊。。。
【在 p*****2 的大作中提到】
:
: uniVar(root->left, num) && !diffVar(root, root->left)
: && uniVar(root->right,num) && !diffVar(root, root->right)
: 这句，如果uniVar returns false。会不会有问题？
|
l*********8
发帖数: 4642 | 18 呵呵，再改就更和二爷的一样了。 要把递归提出去保证执行。
【在 l*********8 的大作中提到】
: 说的对！ 还是我之前错误代码犯得错误！ 在同一个地方摔倒了两次啊。。。
|
p*****2
发帖数: 21240 | 19
其实我也犯了这个错误了。我测试结果不对，呵呵。所以我说这题一遍能写对真的是大
牛了。
【在 l*********8 的大作中提到】
: 说的对！ 还是我之前错误代码犯得错误！ 在同一个地方摔倒了两次啊。。。
|
g*****e
发帖数: 282 | 20 也凑个热闹，假设tree nodes的值都是正整数。如果subtree是null认为root（即null
）值是0，非unival sub tree的node是-1.
int count=0;
getUnivalNode(root);
int getUnivalNode(node root)
{
if (root == null)
{
return 0;
}
int left = getUnivalNode(root.left);
int right = getUnivalNode(root.right);
if ((left == 0 || left == root.val)
&& (right == 0 || right == root.val))
{
count++;
return root.val;
}
return -1;
}
【在 p*****2 的大作中提到】
:
: 其实我也犯了这个错误了。我测试结果不对，呵呵。所以我说这题一遍能写对真的是大
: 牛了。
|
|
|
p*****2
发帖数: 21240 | 21
null
测过吗？
【在 g*****e 的大作中提到】
: 也凑个热闹，假设tree nodes的值都是正整数。如果subtree是null认为root（即null
: ）值是0，非unival sub tree的node是-1.
: int count=0;
: getUnivalNode(root);
: int getUnivalNode(node root)
: {
: if (root == null)
: {
: return 0;
: }
|
c*****a
发帖数: 808 | 22 不知道行不行，只测试了几个case
public static int findUni(BSTNode node){
if(node == null) return 0;
if((node.left==null || node.left.data == node.data) &&
(node.right==null ||node.right.data == node.data))
return findUni(node.left) + findUni(node.right) + 1;
else return findUni(node.left) +findUni(node.right);
} |
l*********8
发帖数: 4642 | 23 反例
2
\
2
\
3
答案是0， 你返回1
【在 c*****a 的大作中提到】
: 不知道行不行，只测试了几个case
: public static int findUni(BSTNode node){
: if(node == null) return 0;
: if((node.left==null || node.left.data == node.data) &&
: (node.right==null ||node.right.data == node.data))
: return findUni(node.left) + findUni(node.right) + 1;
: else return findUni(node.left) +findUni(node.right);
: }
|
c*****a
发帖数: 808 | 24
不知道是不是我理解错了。这个树里面，那个3是不是?我看题目里面的例子每个child
都算1个
【在 l*********8 的大作中提到】
: 反例
: 2
: \
: 2
: \
: 3
: 答案是0， 你返回1
|
d******i
发帖数: 76 | 25
答案是1
From wiki: "A subtree of a tree T is a tree consisting of a node in T and
all of its descendants in T, ... each node is the root node of the subtree
it determines"
叶子节点自身也可为一个subtree，只不过没有descendants。
所以 节点 3 是unival substree
【在 l*********8 的大作中提到】
: 反例
: 2
: \
: 2
: \
: 3
: 答案是0， 你返回1
|
l*********8
发帖数: 4642 | 26 不好意思，我说错了。答案应该是1.
你测试这个case的结果是多少？
child
【在 c*****a 的大作中提到】
:
: 不知道是不是我理解错了。这个树里面，那个3是不是?我看题目里面的例子每个child
: 都算1个
|
c*****a
发帖数: 808 | 27 看了上面的code， 我的code应该错了，我的只检查每2个level
2
2 2
2 2
2 2
1 1
应该会出错 |
m**********0
发帖数: 356 | 28 可不可以解释一下，我怎么看不出来问题呢(godlike的code)？谢谢！
【在 p*****2 的大作中提到】
:
: null
: 测过吗？
|
g*****e
发帖数: 282 | 29 板上讨论的几个例子都测了，过了。。。
【在 m**********0 的大作中提到】
: 可不可以解释一下，我怎么看不出来问题呢(godlike的code)？谢谢！
|
