Naitong Yu

思索与前行

二叉树的遍历(前序、中序、后序、层次)

基本性质

每个结点最多有两棵子树,左子树和右子树,顺序不可颠倒。

  1. 非空二叉树第\(n\)层最多有\(2^{n-1}\)个元素。
  2. 深度为\(h\)的二叉树,至多有\(2^h-1\)个结点。

结点结构

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode(int x) { val = x; }
}

二叉树的遍历

遍历即将树的所有结点都访问且仅访问一次。按照根结点访问次序的不同,可以分为前序遍历,中序遍历,后序遍历。

  • 前序遍历:根结点 -> 左子树 -> 右子树
  • 中序遍历:左子树 -> 根结点 -> 右子树
  • 后序遍历:左子树 -> 右子树 -> 根结点

另外还有一种层次遍历,即每一层都从左向右遍历。

例如:求下图的二叉树的遍历

前序遍历:abdefgc
中序遍历:debgfac
后序遍历:edgfbca
层次遍历:abcdfeg

Count of Smaller Numbers After Self

算法描述

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].

Example:

Given nums = [5, 2, 6, 1]
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Return the array [2, 1, 1, 0].

Fenwick Tree

简介

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)的时间内计算前缀和。