Skip to main content
 首页 » 编程设计

python之n叉树的后序遍历

2024年11月24日12duanxz

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

请您参考如下方法:

这是一个iteration版本,我使用了stack:

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   

还有一个做后序的想法是改变结果,比如把结果插入到head中。

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


我已经在我的 github 中总结了上述算法的代码模板。
如果您对以下内容感兴趣,请观看: https://github.com/recnac-itna/Code_Templates