第3题-小美的红黑树

ID: 920

Difficulty: 5

所属公司 : 美团

时间 :2024年4月13日

题目描述

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

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

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

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

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