bloomberg 面试过经

single value tree
give a binary tree write a program to count the number of single value tree

     5
  /.    \
 1       5
/  \.      \
5. 5.      5.

return 4

可以traverse整个树然后每个节点往下判断是否所有node都有相同的值就是n^2

O(n)我觉得是要保存一个全局count值然后分治的方法加一些判断条件返回一个bool值
bool left / right
if either left or right is false return false

  1. 左子树不空且左val !=root val return false
  2. 右不空且右val != root val return false

count++
return true

如果不满足一切false的条件则要么是leaf node 要么是满足条件的树则每次在return true前count加一