第3题-小美的红黑树

会员专享

请先登录，开通会员或购买该题目所属题库（美团机考编程题库），可解锁完整内容。

购买题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（美团机考编程题库），可解锁完整内容。

购买题库开通会员

思路：树形DFS

本题其实就是统计子树中有多少个节点既有红色节点，又有黑色节点。我们可以自顶向下来进行DFS

遍历到 $u$ 节点时，首先根据 $u$ 节点是红/黑，来对变量进行初始化

然后我们可以遍历 $u$ 的所有子节点，去将以 $u$ 为根节点的红/黑节点数量进行累加计算。

最后判断以 $u$ 为子树的根节点的红色和黑色节点数量是否都大于0，若大于0，则答案+1

小美有一棵有 $n$ 个节点的树，根节点为1号节点，树的每个节点是红色或者黑色，她想知道有多少节点的子树中同时包含红点和黑点。