1D Mark II shutter count# PhotoGear - 摄影器材
d*i
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;
}
这道题很简单，对于还是菜鸟的我还是很难的，发个帖子，供大家讨论，希望最
终得出正确的答案吧。
“我面的时候有一简单题一定要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;
}
