5.二叉查找树

题目描述

二叉查找树是一种特殊的二叉树（每个节点最多只有两个儿子的树）。树的每个节点上存有一个唯一的值，并且满足：这个节点的左子树内所有点的值都比这个节点的值要小，且右子树内所有点的值都比这个节点的值要大。

对于一棵二叉查找树 $T$ ，我们可以将一个值为 $val$ 的新点插入 $T$ 中，且保持树的性质。算法如下：

需要将 $val$ 插入二叉查找树 $T$ 时，执行 $insert(root, val)$ 。

现在有 $N$ 个数需要插入一棵空树中。给定插入序列，请在每个元素被插入之后，输出所有节点的深度总和（根的深度为 $0$ ）。

输入的第一行一个整数 $n$ ，表示序列长度。

以下 $n$ 行是序列中的数字，这些数字是各不相同的，在 $[1,n]$ 区间。

输出 $n$ 行，第 $i$ 行整数表示第 $i$ 个数插入树后，至这个节点的节点深度总和。

对于 $100\%$ 的数据， $N \leq 3 \times 10^{5}$ 。