題目：

給定一顆二叉樹的頭節點head，完成二叉樹的先序、中序和后序遍歷，如果二叉樹的節點為N,則要求時間復雜度為O(N)，額外空間復雜度為O(1)

Morris遍歷

代碼如下：

def getMorris(Node head):if head == None:returncur = headmostRight = Nonewhile cur!=None:mostRight = cur.leftif mostRight!=None:while mostRight!=None and mostRight.right!=cur:mostRight = mostRight.rightif mostRight.right == None:mostRight.right = curcur = cur.leftcontinueelse:mostRight.right = Nonecur = cur.right # morries 前序遍歷def morriesPre(Node head):if head == None:return cur = headmostRight = Nonewhile cur!=None:mostRight = cur.leftif mostRight!=None:while mostRight!=None and mostRight.right!=cur:mostRight = mostRight.rightif mostRight==None:mostRight.right = curprint(cur.value)cur = cur.leftcontinueelse:mostRight == Noneelse:print(cur.value)cur = cur.right# morries 中序遍歷def morriesIn(Node head):if head == None:return cur = headmostRight = Nonewhile cur!=None:mostRight = cur.leftif mostRight!=None:while mostRight!=None and mostRight.right!=cur:mostRight = mostRight.rightif mostRight==None:mostRight.right = curprint(cur.value)cur = cur.leftcontinueelse:mostRight == Noneprint(cur.value)cur = cur.right # morries 后序def morrieslast(Node head):if head == None:returncur = headmostRight = Nonewhile cur!=None:mostRight = cur.leftif mostRight != None:while mostRight!=None and mostRight.right!=cur:mostRight = mostRight.rightif mostRight == None:mostRight.left = curcur = cur.leftcontinueelse:mostRight.right = NoneprintEdge(cur.left)printEdfe(head)cur = cur.rightdef printEdge(Node head):tail = reverseEdge(head)cur = tailwhile cur!=None:print(cur.value)cur = cur.rightreverseEdge(tail)def reverseEdge(Node from_):pre = Nonenext_ = Nonewhile from_!=None:next_ = from_.rightfrom_.right = prepre = from_from_ = next_return pre

?

總結

以上是生活随笔為你收集整理的遍历二叉树的神级方法(Morris遍历)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。