一、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]