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

基本性质

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

  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

Read more   2016/3/28 posted in  LeetCode

理解 LSTM 网络

循环神经网络(RNN)

人们的每次思考并不都是从零开始的。比如说你在阅读这篇文章时,你基于对前面的文字的理解来理解你目前阅读到的文字,而不是每读到一个文字时,都抛弃掉前面的思考,从头开始。你的记忆是有持久性的。

传统的神经网络并不能如此,这似乎是一个主要的缺点。例如,假设你在看一场电影,你想对电影里的每一个场景进行分类。传统的神经网络不能够基于前面的已分类场景来推断接下来的场景分类。

循环神经网络(Recurrent Neural Networks)解决了这个问题。这种神经网络带有环,可以将信息持久化。

Recurrent Neural Networks have loops.

Read more   2016/3/21 posted in  Neural Networks

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

Read more   2016/2/14 posted in  LeetCode

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

Read more   2016/2/14 posted in  LeetCode

在OpenWRT中配置isatap以及IPv6 NAT的方法

在紫荆公寓这边,由于原生IPv6需要认证才能使用,十分不方便。而使用isatap隧道的方法访问IPv6则十分的稳定。但是由于isatap隧道只能够得到一个GlobalIPv6的地址,因此需要在路由器上启用IPv6 NAT才能够使得路由器后面的设备无缝访问IPv6资源。之前的路由器,在配置好之后稳定地运行了一年有余,前几日因为一些需求,需要重新配置路由器,因此将配置的过程记录下来,供今后参考。

Read more   2015/7/6 posted in  技术

Filco Minilar Air 机械键盘

之前一直觉得自己不是一个器材党,因此,当室友换上了机械键盘的时候,我依然无动于衷。键盘只要够用就好了嘛。之前因为外接显示器的缘故,也给我的 rMBP 配过 Wireless Keyboard,不过在我的外接显示器出掉之后,Wireless Keyboard 就被我收在抽屉里落灰了。因为感觉其手感,跟 rMBP 的内置键盘也差不了多少,既然如此,我何必又要多带一个键盘呢?直接用内置的不就好了嘛。

Read more   2015/4/6 posted in  生活

最水木发布了

最水木 (iZSM) 是专门为 iOS 用户开发的一款水木社区的非官方客户端。该客户端充分利用 iOS 的新特性,给您带来最完美的水木社区使用体验。不管您是资深潜水员,还是水木水车,最水木是您在 iOS 设备上访问水木社区的绝佳的选择!

Read more   2015/3/24 posted in  生活 技术

OS X下在NAT后连接清华IPv6的脚本

由于IPv6是不支持NAT的,因此,默认情况下,宿舍里装上路由器后,就没法再使用学校提供的IPv6服务了。不过难道真的没有办法了么?答案是否定的。将下面的脚本保存后,并执行,就可以在NAT后利用isatap隧道来使用IPv6啦~脚本中的隧道服务器是清华的。

Read more   2013/8/22 posted in  技术

Buffalo wzr-hp-g300nh路由器折腾小记

之前该路由器一直用的是Open-WRT的固件,但是时间长了之后,总是会遇到莫名其妙的Wifi掉线问题,VPN崩掉的问题,可能是因为一直使用开发版的固件的缘故吧。但是稳定版的Backfire固件似乎有问题,我每刷必成砖,每次都要ttl进行修复。好了闲话少提,这次主要记录的是将该路由器刷成Buffalo官方提供的Professional版本的固件,并且配置使用的过程。

Read more   2012/12/7 posted in  技术

Mac OS X下通过ISATAP连接清华的IPv6的方法

紫荆15#这边的网络是v4/v6双栈,可以自动获取到v4和v6的地址,但是鉴于网络中心的某一个项目强行给全校绝大部分ipv6加上了一个前无古人后无来者充分彰显世界一流大学地位巨烂无比经常崩溃的认证系统,并且在可以预见的未来,该认证系统并不会被拿掉,因此我毅然放弃了使用原生的ipv6,而改用没有认证系统的isatap隧道。

Read more   2012/9/8 posted in  技术