阿里23年春招笔试-满二叉树

题目描述

给定一棵二叉树，求这棵二叉树有多少节点满足以该节点为根的子树是满二叉树。一棵树是满二叉树，当且仅当每一层的节点数量都达到了最大值（即无法在这一层添加新节点）。

输入描述

第一行输入一个正整数n，代表节点的数量。

接下来有n行，第i行输入两个整数l和r，代表i行节点的左儿子和右儿子。

⚠️注意：如果一个节点没有左儿子/右儿子，则对应的l/r为-1。（1 <= n <= 10^5）

输出描述

子树为满二叉树的节点数量。

示例一

输入：
5
2 3
4 5
-1 -1
-1 -1

输出：
4

示例说明

2、3、4、5号节点的子树都是满二叉树

思路

构建一个树的数据结构，然后DFS遍历，一个节点为满二叉树当且仅当该节点为叶子，或该节点的左右孩子均为深度相等的满二叉树。