145. 二叉树的后序遍历

一、145. 二叉树的后序遍历 1.1、题目描述

1.2.1、递归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def __init__(self) -> None:
        self.ret = []
    
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        self.pt(root)
        return self.ret
    
    def pt(self, root: TreeNode) -> List[int]:
        if root.left:
            self.pt(root.left)
        if root.right:
            self.pt(root.right)
        
        self.ret.append(root.val)

1.2.2、迭代

class Solution:
    def __init__(self) -> None:
        self.ret = []
    
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        
        que = [root]
        
        while que:
            node = que.pop()
            if node:
                self.ret.append(node.val)
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
        # 先按照先序遍历，然后将结果逆序       
        return self.ret[::-1]