Python编程中的二叉树后序遍历

假设我们有一个二叉树。我们必须使用迭代方法找到这棵树的后序遍历。如果树是这样的：

那么输出将是：[9,15,7,10,-10]

为了解决这个问题，我们将遵循以下步骤：

  • 如果根节点为空，则返回空数组

  • 创建一个数组ret

  • stack := 定义一个包含[root, 0]对的栈

  • 当栈不为空时：

    • node := 栈顶元素，然后从栈中删除该元素。

    • 如果节点对的第二个值是0，则

      • current := 节点对的第一个值

      • 将一个(current, 1)对插入到栈中

      • 如果current的右子节点存在

        • 将一个[current的右子节点, 0]对插入到栈中

      • 如果current的左子节点存在：

        • 将一个[current的左子节点, 0]对插入到栈中

    • 否则，当节点对第一个值的第二个值不为0时，将节点对第一个值的数据插入到res中

  • 返回res

让我们看看下面的实现来更好地理解：

示例

 在线演示

class TreeNode:
def __init__(self, data, left = None, right = None):
   self.data = data
   self.left = left
   self.right = right
def insert(temp,data):
   que = []
   que.append(temp)
   while (len(que)):
      temp = que[0]
      que.pop(0)
      if (not temp.left):
         if data is not None:
            temp.left = TreeNode(data)
         else:
            temp.left = TreeNode(0)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
         if data is not None:
            temp.right = TreeNode(data)
         else:
            temp.right = TreeNode(0)
         break
      else:
         que.append(temp.right)
def make_tree(elements):
   Tree = TreeNode(elements[0])
   for element in elements[1:]:
      insert(Tree, element)
   return Tree
class Solution(object):
   def postorderTraversal(self, root):
      if not root:
         return []
      res = []
      stack = [[root,0]]
      while stack:
         node = stack[-1]
         stack.pop()
         if node[1]== 0 :
            current = node[0]
            stack.append([current,1])
            if current.right:
               stack.append([current.right,0])
            if current.left:
               stack.append([current.left,0])
         else:
            if node[0].data != 0:
               res.append(node[0].data)
      return res
ob = Solution()
root = make_tree([-10,9,10,None,None,15,7])
print(ob.postorderTraversal(root))

输入

[-10,9,10,None,None,15,7]

输出

[9, 15, 7, 10, -10]

更新于：2020年6月9日

179 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告