成都科盛兴网站建设有限公司,英文网站优化,工商注册公司查名,济南中桥信息做的小语种网站怎么样大家好~我叫「小鹿鹿鹿」#xff0c;是本卖萌小屋的第二位签约作#xff08;萌#xff09;者#xff08;货#xff09;。和小夕一样现在在从事NLP相关工作#xff0c;希望和大家分享NLP相关的、不限于NLP的各种小想法#xff0c;新技术。这是我的第一篇试水文章#xf… 大家好~我叫「小鹿鹿鹿」是本卖萌小屋的第二位签约作萌者货。和小夕一样现在在从事NLP相关工作希望和大家分享NLP相关的、不限于NLP的各种小想法新技术。这是我的第一篇试水文章初来乍到希望大噶多多滋辞(●◡●)。冬天已经来了秋招早已悄无声息的结束。作为一个已经工作了两年的老人校招面试感觉就像高考一样遥远。但是呢虽然工作了还是要时刻保持危机感的呀万一哪天就要跳槽了呢(∇)。遥想当年面试的时候由于没有学过数据结构在面试官出算法题之前就老实交待家底“我的算法和数据结构不太行树呀图呀都不太会(✿◡‿◡)。但是经过两年断断续续的学习发现其实树是一个套路非常明显的一类算法题而遍历树是解决绝大多数树问题的基础很多题目都是在树的遍历上扩展下面小鹿就以树的遍历为例解剖树里面深深的套路吧o(*▽*)o。 树的基础回顾二叉树长什么样子小鹿这里就不上图啦所谓的根节点、叶子节点也不介绍啦。我们知道二叉树的遍历分为三种前序、中序和后序。这三种序的不同主要就是在于什么时候访问根节点。以前序为例在遍历一颗树的时候先访问根节点再遍历其根节点的左子树最后访问根节点的右子树。而中序遍历就是先遍历左子树再访问根节点最后遍历右子树后序遍历小鹿就不重复啦。树的递归树有一个很好的特性就是一棵树的根节点的左右子树仍然是一颗树这好像是一句正确的废话╮(▽)╭所以我们可以把一棵复杂的大树分解成两颗稍微小一点的树依次类推最后变成最小的单元只有一个节点的树。不管怎么讲处理只有一个节点的树是不是超级容易这个呢就是递归的思想所以说到这里我们以后只要遇到关于树的问题谁还不会用递归走一波呢下面就来开始实践用递归的思想实现二叉树的前序、中序、后序遍历遍历结果记录在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.ansdef inorderStack(self, root):stack []p rootwhile p:stack.append(p)p p.leftwhile stack:p stack.pop()self.ans.append(p.val)p p.rightwhile p:stack.append(p)p p.leftreturn self.ansdef postorderStack(self, root)aStack []prev Nonep rootwhile aStack or p:if p:aStack.append(p)p p.leftelse:p aStack[-1]if p.right prev or p.right is None:self.ans.append(p.val)prev paStack.pop()p Noneelse:p p.right return self.ans
用栈来实现树的遍历就稍微复杂一点啦。首先前序是最简单的我们用一个栈first-in-last-out来维护树遍历的顺序。初始状态是把非空的根节点push到栈中逐个从栈中取出节点访问其值然后先push右节点再push左节点到栈中就保证访问顺序是 root-left-right 啦。超级简单有木有中序遍历就稍微难一些了在访问一个节点之前需要访问其 left-most 节点将其左节点逐个加入到栈中直到当前节点为None。然后从栈中取出节点由于栈的特性在取出某个节点之前其左节点已经被访问所以就可以安心的访问该节点然后把当前节点置为其右节点依次类推。后序遍历和中序遍历差不多在中序遍历的基础上需要增加一个prev记录上一个访问的节点确认在访问某个节点之前其右节点是否已经被访问。用栈的方式遍历树更加显式的告诉了大家树遍历的时候是怎么回溯的其时间空间复杂度仍然是O(n)。Morris遍历下面小鹿要给大家介绍一个神级树遍历方法Morris使其空间复杂度从O(n)变成O(1)!树的遍历一个难点就是确定什么时候以及回溯如何回溯好像是两个点第一种递归的方法通过函数的嵌套实现回溯第二种方法通过栈存储节点的顺序实现回溯而Morris则是利用树中空节点记录每个节点其回溯的节点实现空间复杂度为O(1)的遍历。具体来说当我们访问了某个左子树最右的节点后需要回溯到其左子树的根节点但是怎么回去呢我们需要在之前加一个链接将该根节点连到其左子树的最右节点的右节点上。是不是有点绕呢(╯﹏╰)b不慌小鹿带你一起做一遍中序遍历的例子就清楚啦~~以上面的图为例做中序遍历当前节点为6curr6时找到其左子树的最右节点5添加链接备用这样从节点5我们就可以回溯到节点6。更新当前节点curr2重复相同的操作。当curr1时到达叶子节点输出(节点变蓝)因为之前添加了链接所以可以从节点1回溯到节点2回溯删除链接。当前节点变成4以此类推下去已经懵逼的小伙伴们请仔细品味下面的代码(▽)class Solution(object):def __init__(self):self.ans []def inorderMorris(self, root):p rootwhile p:if p.left is None:#left-most nodeself.ans.append(p.val)p p.rightelse:#find prev, the right-most node of the left treeprev p.leftwhile prev.right and prev.right ! p:prev prev.rightif prev.right is None:#first time to visit pprev.right p #add linkp p.leftelse:#second time to visit pself.ans.append(p.val)prev.right Nonep p.rightreturn self.ansdef preorderMorris(self, root):p rootprev Nonewhile p:if p.left is None:#left-most nodeself.ans.append(p.val)p p.rightelse:#find right-most node of the left treeprev p.leftwhile prev.right and prev.right ! p:prev prev.rightif prev.right is None:#first time to visit pprev.right p #add linkself.ans.append(p.val)p p.leftelse:#second time to visit pp p.right #back to rootprev.right None #delete the linkreturn 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 Noneclass Solution(object):def __init__(self):self.ans []def postorderMorris(self, root):dump TreeNode(0)dump.left rootp dumpwhile p:if p.left is None:p p.rightelse:prev p.leftwhile prev.right and prev.right ! p:prev prev.rightif prev.right is None:#first time to visit pprev.right pp p.leftelse:#second time to visit pself.singleLinkReverseTraversal(p.left, prev)prev.right Nonep p.rightreturn self.ansdef singleLinkReverseTraversal(self, start, end):#take the right branch from start to end as single link#travel reverselyif start end:self.ans.append(start.val)returnself.reverse(start, end)curr endwhile curr ! start:self.ans.append(curr.val)curr curr.rightself.ans.append(curr.val)self.reverse(end, start)def reverse(self, start, end):if start end:returnprev Nonecurr startwhile curr ! end:tmp curr.rightcurr.right prevprev currcurr tmpcurr.right prev
眼尖的小伙伴看了代码之后就会发现Morris后序遍历怎么多了两个函数怎么和前序和中序不一样了呢ヽ(Д´)这个Morris后序遍历确实比较挺难理解我们还是用最简单的图示来走一遍代码的意思吧~~~开始除了加了一个dump节点以外都是一样的一路向下到达left-most节点3不输出注意啦不一样啦然后回溯到节点2逆序输出从3到3的节点删除链接。从节点2一路往右回溯到节点1逆序输出从其左节点2到prev节点6删除节点。以此类推就噢啦ヽ(▽)。 现在大家都清楚了吧~~不清楚的地方欢迎在评论区提出噢小鹿会尽最大努力为大家答疑解惑嗒(▽)后面小鹿鹿鹿还会持续推送关于算法和数据结构的小文章大家有兴趣的话欢迎关注订阅哦(´▽) 。感谢大家的阅读[]~(▽)~*鞠躬
