题解 | 二叉树的后序遍历

from ctypes import resize
import queue
from queue import Queue
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型一维数组
#
class Solution:
    # #法1：递归法 左右根
    # def postorder(self,root:TreeNode,res:List[int]):
    #     if not root:
    #         return 
    #     else:
    #         self.postorder(root.left,res)#左递归
    #         self.postorder(root.right,res)#右子树递归
    #         res.append(root.val)#添加根节点

    # def postorderTraversal(self , root: TreeNode) -> List[int]:
    #     # write code here
    #     res=[]
    #     self.postorder(root,res)
    #     return res

    # 法2：根据栈先进后出的特性
# 1：开辟一个辅助栈，用于记录要访问的子节点，开辟一个前序指针pre。
# 2：从根节点开始，每次优先进入每棵的子树的最左边一个节点，我们将其不断加入栈中，用来保存父问题。(同中序遍历)
# 3：弹出一个栈元素，看成该子树的根，判断这个根的右边有没有节点或是有没有被访问过，如果没有右节点或是被访问过了，可以访问这个根，并将前序节点标记为这个根。

# 4：如果没有被访问，那这个根必须入栈，进入右子树继续访问，只有右子树结束了回到这里才能继续访问根。


    def postorderTraversal(self , root: TreeNode) -> List[int]:
    # write code here
        res,stack=[],[]
        pre=None#用于标记右子树是否被访问过

        while stack or root:
            #找到当前节点最左的节点
            while root:
                stack.append(root)#父节点放入栈中
                root=root.left    #找其左子树
            
            stack_top=stack[-1]#取栈顶元素
            stack.pop()

            #与中序遍历不同的地方
            if not stack_top.right or stack_top.right is pre:
            #若当前节点没有右子树或者右子树已被访问过
            #将当前节点添加到答案序列中
                res.append(stack_top.val)
                pre=stack_top#修改pre为当前节点

            else:
                #重新将该节点入栈
                stack.append(stack_top)
                #进入右子树遍历
                root=stack_top.right

        return res