Auto Byte

Science AI

# 算法与数据结构--空间复杂度O(1)遍历树

````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````

Morris遍历

````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````