Case 1st 最少的摄像头——亚马逊面试问题
给定一个二叉树，我们在树的节点上安装摄像头 。
节点上的每个摄像机都可以监视其父级、自身及其直接子级 。
计算监视树的所有节点所需的最小摄像机数 。
例：
Input: [0,0,null,0,0]
Output: 1
Explanation: One camera is enough to monitor all nodes if placed as shown.

了解问题：
由于我们希望尽量减少相机的数量，因此有一点很清楚，我们不会将相机放置在叶节点上 。
所以我们可以从叶子到根追溯 。这使得DFS成为解决问题的最可能选择 。
但是当我们回溯时，我们需要在节点之间交换信息，以查看当前节点是否需要摄像头 。
如果上一个节点已经有摄像头，我们不需要摄像头 。总而言之，我们需要考虑以下事项：
如果当前节点是叶节点，则我们不需要相机 。
如果我们在当前节点上没有摄像头，那么父节点需要它 。
如果当前节点具有相机，则其父节点不需要相机 。
我们可以分配不同的值来指示这些状态 。-1 从孩子的意思是放相机 。1 来自任何孩子意味着没有相机 。
代码实现：
# Definition for a binary tree node.
# class TreeNode:
#def __init__(self, val=0, left=None, right=None):
#self.val = val
#self.left = left
#self.right = right
class Solution:
def minCameraCover(self, root: TreeNode) -> int:
def dfs(node):
l=0
r=0
if (node.left is None and node.right is None):
return -1
if node.left:
l = dfs(node.left)
if node.right:
r = dfs(node.right)
if(l == -1 or r == -1):
self.count += 1
return 1
if(l == 0 and r == 0):
return -1
if(l == 1 or r == 1):
return 0
self.count=0
cams = dfs(root)
if(cams == -1):
self.count += 1
return self.count

复杂性分析
时间复杂度：O（N），其中 N 是二叉树中的节点数
空间复杂性：递归调用堆栈的空间，可能是 N
Case 2nd 族谱
了解到家族成员的代际关系，我们想透过图的关系信息输入，返回任意某人是第几代？
英伟达和AMD之间是否存在完全竞争？下图显示了黄仁勋和苏丽莎家谱显示他们的关系有多密切？
如何构造恰当的数据结构？
1、构造家庭成员的class类
2、追加家庭成员的信息对应到树连接节点
3、如何输出打印
class类
class FamilyMember:
def __init__(self, name, gender, generation):
self.name = name
self.gender = gender
self.generation = generation
self.children = []
self.parents = []

# 家族根
root = FamilyMember("John", "Male", 0)
# John 的子女
child1 = FamilyMember("Jane", "Female", 1)
child2 = FamilyMember("Mike", "Male", 1)
root.children.append(child1)