python - 一元树的后序遍历

标签 python iteration

我需要以下代码的帮助来回答。我正在尝试使用堆栈而不是递归在n元树上执行后置遍历,因为python的限制为1000个递归。我在极客身上找到了相同“ https://www.geeksforgeeks.org/iterative-preorder-traversal-of-a-n-ary-tree/”的预遍历代码。但是我无法将其隐藏到后期订购中。任何帮助都会很棒。

最佳答案

这是我使用的iterationstack版本:

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.children = []

def postorder_traversal_iteratively(root: 'TreeNode'):
    if not root:
        return []
    stack = [root]
    # used to record whether one child has been visited
    last = None

    while stack:
        root = stack[-1]
        # if current node has no children, or one child has been visited, then process and pop it
        if not root.children or last and (last in root.children):
            '''
            add current node logic here
            '''
            print(root.val, ' ', end='')

            stack.pop()
            last = root
        # if not, push children in stack
        else:
            # push in reverse because of FILO, if you care about that
            for child in root.children[::-1]:
                stack.append(child)



测试代码和输出:

n1 = TreeNode(1)
n2 = TreeNode(2)
n3 = TreeNode(3)
n4 = TreeNode(4)
n5 = TreeNode(5)
n6 = TreeNode(6)
n7 = TreeNode(7)
n8 = TreeNode(8)
n9 = TreeNode(9)
n10 = TreeNode(10)
n11 = TreeNode(11)
n12 = TreeNode(12)
n13 = TreeNode(13)

n1.children = [n2, n3, n4]
n2.children = [n5, n6]
n4.children = [n7, n8, n9]
n5.children = [n10]
n6.children = [n11, n12, n13]

postorder_traversal_iteratively(n1)



可视n元树和输出:

                   1
                 / | \
                /  |   \
              2    3     4
             / \       / | \
            5    6    7  8  9
           /   / | \ 
          10  11 12 13

# output: 10  5  11  12  13  6  2  3  7  8  9  4  1  




进行后期订购的另一个想法是更改结果,例如将结果插入头部。

它的效率较低,但易于编码。您可以在here中找到一个版本



我在github中为上述算法总结了code templates
如果您对以下内容感兴趣,请观看:
https://github.com/recnac-itna/Code_Templates

关于python - 一元树的后序遍历,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55606017/

相关文章:

python - 使用opencv python从表单中检测复选框

python - 动态获取模块

python - Pandas 迭代更新列值

python - 将 HOG+SVM 训练应用于网络摄像头以进行目标检测

python - 使用 spines 在 matplotlib 中仅自定义刻度线的一侧

javascript - 如何将数组项一一添加到 DOM?

python - 使用Scrapy迭代表单

Python同时迭代两个列表

python - 派生类无法识别父类的方法参数

python - 递归函数的迭代版本