题解 | #二叉树的后序遍历#

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型一维数组
#
class Solution:
    # def postorderTraversal(self , root: TreeNode) -> List[int]:
    #     # write code here
    #     """ method_1: 左右根， 递归后序遍历
    #     """
    #     rsta = list()
    #     self.postorder(rsta, root)
    #     return rsta
    #     pass

    # def postorder(self, rsta: List[int], root: TreeNode):
    #     if root == None:
    #         return []

    #     self.postorder(rsta, root.left)
    #     self.postorder(rsta, root.right)
    #     rsta.append(root.val)

    
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        """
        method_2: 二叉树后序遍历，非递归。
        步骤： 
        step1: 开辟一个辅助栈， 记录要访问的 子节点，开辟一个前序指针pre
        step2: 从根节点开始，每次优先进入每棵紫薯的最左边的一个节点，将其不断加入栈中， 用于保存父节点；
        step3: 弹出一个栈元素，堪称该子树的根，判断这个根的右边有无节点或是有没有被访问过，如果没有有节点或是被访问过，可以访问这个根，并将前序节点标记为这个根
        step4: 如果没有被访问，那么这个根必须入栈， 进入右子树继续访问，只有右子树结束了回到这里才能继续访问根。
        """
        rsta = list()
        tmp_stack = list()
        pre = None
        while root or tmp_stack:
            while root:
                tmp_stack.append(root)
                root = root.left
            node = tmp_stack[-1]
            tmp_stack.pop()

            if not node.right or node.right is pre:
                rsta.append(node.val)
                pre = node
            else:
                tmp_stack.append(node)
                root = node.right
        return rsta

        return rsta
        pass
		 二叉树的后序遍历，递归和非递归写法