题解 | 二叉树的后序遍历-leetcode 题解

from os import NGROUPS_MAX
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型一维数组
#
class Solution:
    def postorderTraversal_1(self , root: TreeNode) -> List[int]:
        # write code here
        # 递归： 左子树不为空 递归左子树  右子树不为空 递归右子树
        res=[]
        if root is None:
            return res 
        def  dfs(root):
            if root.left: # 左子树不为空
                dfs(root.left)  
            if root.right: # 右子树不为空
                dfs(root.right)
            res.append(root.val)
        dfs(root)
        return res 
    def postorderTraversal(self , root: TreeNode) -> List[int]:
        stack=[]
        res=[]
        if root is None:
            return res 
        prev=None
        while len(stack)>0 or  root is not None:
            while root:
                stack.append(root)
                root=root.left 
            root =stack.pop()
            if root.right is None  or root.right==prev:  # 再次回到根节点 
                # 记录结果
                res.append(root.val)
                prev=root 
                root= None 
            else:
                stack.append(root)
                root=root.right
        return res