题目描述

塔子哥有一棵节点数为 $n$ 的完整二叉树，对于一个完整二叉树的定义是：要么每个节点有两个子节点，要么每个节点没有子节点。

• 没有子节点的节点，其权值为 $1$ 。

思路：深度优先搜索

定义 dfs(u) 表示 u 的权值。

如果 u 有两个子节点，则先计算两个子节点的权值，然后进行对应的运算得到 u 的权值。 如果 u 没有子节点，则 u 的权值为 $1$ 。

时间复杂度：$O(n)$

cpp