用循环遍历树

树的遍历用递归法最为简便，那么用循环该如何实现呢?

image.png

1. 用循环方法后序遍历树。
   递归的本质是用了栈结构，不能用递归就自己用栈来实现递归的效果。后序遍历的话越上层越后输出，同一层越靠右越后输出。那么进栈时就是上层先进，同一层右侧先进栈。

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""
class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        if root is None:
            return None
        result = []
        stodo = [root]
        while stodo:
            c_node = stodo.pop()
            stodo.extend(c_node.children)
            result.append(c_node.val)
        return reversed(result)   

stodo用来实现先处理右侧，保存结果的result栈要倒序才是正确的输出顺序。