二叉树的遍历(前序、中序、后序、层次)
基本性质
每个结点最多有两棵子树,左子树和右子树,顺序不可颠倒。
- 非空二叉树第\(n\)层最多有\(2^{n-1}\)个元素。
- 深度为\(h\)的二叉树,至多有\(2^h-1\)个结点。
每个结点最多有两棵子树,左子树和右子树,顺序不可颠倒。
You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i]
is the number of smaller elements to the right of nums[i]
.
Fenwick Tree 又叫二分索引树(Binary Index Tree),是一种树状结构的数组。该数据结构是由 Peter M. Fenwick 在1994年首次提出来的。最初,Fenwick Tree 被设计用于数据压缩,而现今,该数据结构主要用来存储频次信息或者用于计算累计频次表等。
对于普通的数组,更新数组中的某一元素需要O(1)
的时间,计算数组的第n
项前缀和(即前n
项和)需要O(n)
的时间。而 Fenwick Tree 可以在O(log n)
的时间内更新结点元素,在O(log n)
的时间内计算前缀和。