算法与数据结构--空间复杂度O(1)遍历树
大家好~我叫「小鹿鹿鹿」，是本卖萌小屋的第二位签约作（萌）者（货）。和小夕一样现在在从事NLP相关工作，希望和大家分享NLP相关的、不限于NLP的各种小想法，新技术。这是我的第一篇试水文章，初来乍到，希望大噶多多滋辞(●'◡'●)。
冬天已经来了，秋招早已悄无声息的结束。作为一个已经工作了两年的老人，校招面试感觉就像高考一样遥远。但是呢，虽然工作了，还是要时刻保持危机感的呀，万一哪天就要跳槽了呢(￣∇￣)。
树的基础回顾
二叉树长什么样子，小鹿这里就不上图啦，所谓的根节点、叶子节点也不介绍啦。我们知道，二叉树的遍历分为三种：前序、中序和后序。这三种序的不同主要就是在于什么时候访问根节点。以前序为例，在遍历一颗树的时候先访问根节点，再遍历其根节点的左子树，最后访问根节点的右子树。而中序遍历就是先遍历左子树，再访问根节点，最后遍历右子树；后序遍历小鹿就不重复啦。
树的递归
树有一个很好的特性，就是一棵树的根节点的左右子树仍然是一颗树
这好像是一句正确的废话╮(￣▽￣"")╭
所以我们可以把一棵复杂的大树，分解成两颗稍微小一点的树，依次类推，最后变成最小的单元（只有一个节点的树）。不管怎么讲，处理只有一个节点的树是不是超级容易！！！这个呢就是递归的思想，所以说到这里，我们以后只要遇到关于树的问题，谁还不会用递归走一波呢！
下面就来开始实践！用递归的思想实现二叉树的前序、中序、后序遍历（遍历结果记录在self.ans的向量里）。小鹿这里就用python写啦（真的不要纠结编程语言噢）。遍历一个有n个节点的树，其时间复杂度和空间复杂度都是O(n)。
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: self.inorderRecursive(root.left) self.ans.append(root.val) self.inorderRecursive(root.right)
def postorderRecursive(self, root): if root: self.postorderRecursive(root.left) self.postorderRecursive(root.right) self.ans.append(root.val)树和栈
class Solution(object): def __init__(self): self.ans = [] def preorderStack(self, root): aStack = [] if root: aStack.append(root) while aStack: p = aStack.pop() self.ans.append(p.val) if p.right: aStack.append(p.right) if p.left: aStack.append(p.left) return self.ans
def inorderStack(self, root): stack = [] p = root while p: stack.append(p) p = p.left while stack: p = stack.pop() self.ans.append(p.val) p = p.right while p: stack.append(p) p = p.left return self.ans
def postorderStack(self, root) aStack = [] prev = None p = root while aStack or p: if p: aStack.append(p) p = p.left else: p = aStack[-1] if p.right == prev or p.right is None: self.ans.append(p.val) prev = p aStack.pop() p = None else: p = p.right return self.ans用栈来实现树的遍历就稍微复杂一点啦。首先前序是最简单的，我们用一个栈（first-in-last-out）来维护树遍历的顺序。初始状态是把非空的根节点push到栈中，逐个从栈中取出节点，访问其值，然后先push右节点再push左节点到栈中，就保证访问顺序是 root->left->right 啦。超级简单有木有！
中序遍历就稍微难一些了，在访问一个节点之前需要访问其 left-most 节点，将其左节点逐个加入到栈中，直到当前节点为None。然后从栈中取出节点，由于栈的特性，在取出某个节点之前，其左节点已经被访问，所以就可以安心的访问该节点，然后把当前节点置为其右节点，依次类推。
Morris遍历
下面小鹿要给大家介绍一个神级树遍历方法Morris，使其空间复杂度从O(n)变成O(1)!
已经懵逼的小伙伴们请仔细品味下面的代码(￣▽￣)～
class Solution(object): def __init__(self): self.ans = [] def inorderMorris(self, root): p = root while p: if p.left is None: #left-most node self.ans.append(p.val) p = p.right else: #find prev, the right-most node of the left tree prev = p.left while prev.right and prev.right != p: prev = prev.right if prev.right is None: #first time to visit p prev.right = p #add link p = p.left else: #second time to visit p self.ans.append(p.val) prev.right = None p = p.right return self.ans def preorderMorris(self, root): p = root prev = None while p: if p.left is None: #left-most node self.ans.append(p.val) p = p.right else: #find right-most node of the left tree prev = p.left while prev.right and prev.right != p: prev = prev.right if prev.right is None: #first time to visit p prev.right = p #add link self.ans.append(p.val) p = p.left else: #second time to visit p p = p.right #back to root prev.right = None #delete the link return self.ans Morris前序遍历和中序遍历几乎一模一样，唯一的差别就是在第一次访问节点的时候就输出，还是第二次访问节点的时候输出。Morris后序遍历在此基础上还要稍微的复杂一丢丢。因为后续遍历根节点最后输出，需要增加一个dump节点作为假的根节点，使其的左子树的 right-most 指向原来的根节点。话不多说，我们来看下代码吧！
# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = None
class Solution(object): def __init__(self): self.ans = []
def postorderMorris(self, root): dump = TreeNode(0) dump.left = root p = dump while p: if p.left is None: p = p.right else: prev = p.left while prev.right and prev.right != p: prev = prev.right if prev.right is None: #first time to visit p prev.right = p p = p.left else: #second time to visit p self.singleLinkReverseTraversal(p.left, prev) prev.right = None p = p.right return self.ans
def singleLinkReverseTraversal(self, start, end): #take the right branch from start to end as single link #travel reversely if start == end: self.ans.append(start.val) return
self.reverse(start, end) curr = end while curr != start: self.ans.append(curr.val) curr = curr.right self.ans.append(curr.val) self.reverse(end, start)
def reverse(self, start, end): if start == end: return prev = None curr = start while curr != end: tmp = curr.right curr.right = prev prev = curr curr = tmp curr.right = prev