算法与数据结构--空间复杂度O(1)遍历树
原创
⼩⿅⿅⿅
2019-11-17⼣⼩瑶的卖萌屋
⼤家好~我叫「⼩⿅⿅⿅」，是本卖萌⼩屋的第⼆位签约作（萌）者（货）。和⼩⼣⼀样现在在从事NLP相关⼯作，希望和⼤家分
享NLP相关的、不限于NLP的各种⼩想法，新技术。这是我的第⼀篇试⽔⽂章，初来乍到，希望⼤噶多多滋辞(●'◡'●)。
冬天已经来了，秋招早已悄⽆声息的结束。作为⼀个已经⼯作了两年的⽼⼈，校招⾯试感觉就像⾼考⼀样遥远。但是呢，虽然⼯作
了，还是要时刻保持危机感的呀，万⼀哪天就要跳槽了呢(￣∇￣)。
遥想当年⾯试的时候，由于没有学过数据结构，在⾯试官出算法题之前就⽼实交待家底：“我的算法和数据结构不太⾏，树呀图呀都
不太会(✿◡‿◡)"。但是经过两年断断续续的学习，发现其实树是⼀个套路⾮常明显的⼀类算法题，⽽遍历树是解决绝⼤多数树问题
的基础（很多题⽬都是在树的遍历上扩展），下⾯⼩⿅就以树的遍历为例，解剖树⾥⾯深深的套路吧o(*￣▽￣*)o。
树的基础回顾
⼆叉树⻓什么样⼦，⼩⿅这⾥就不上图啦，所谓的根节点、叶⼦节点也不介绍啦。我们知道，⼆叉树的遍历分为三种：前序、中序
和后序。这三种序的不同主要就是在于什么时候访问根节点。以前序为例，在遍历⼀颗树的时候先访问根节点，再遍历其根节点的
左⼦树，最后访问根节点的右⼦树。⽽中序遍历就是先遍历左⼦树，再访问根节点，最后遍历右⼦树；后序遍历⼩⿅就不重复啦。
树的递归
树有⼀个很好的特性，就是⼀棵树的根节点的左右⼦树仍然是⼀颗树
这好像是⼀句正确的废话╮(￣▽￣"")╭
所以我们可以把⼀棵复杂的⼤树，分解成两颗稍微⼩⼀点的树，依次类推，最后变成最⼩的单元（只有⼀个节点的树）。不管怎么
讲，处理只有⼀个节点的树是不是超级容易！！！这个呢就是递归的思想，所以说到这⾥，我们以后只要遇到关于树的问题，谁还
不会⽤递归⾛⼀波呢！
下⾯就来开始实践！⽤递归的思想实现⼆叉树的前序、中序、后序遍历（遍历结果记录在self.ans的向量⾥）。⼩⿅这⾥就⽤python
写啦（真的不要纠结编程语⾔噢）。遍历⼀个有n个节点的树，其时间复杂度和空间复杂度都是O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def __init__(self)
:
self.ans = []
def preorderRecursive(self, root)
:
if root
:
self.ans.append(root.val)
self.preorderRecursive(root.left)
self.perorderRecursive(root.right)
def inorderRecursive(self, root)
:
if root
