LeetCode算法题|LeetCode —— 145. 二叉树的后序遍历【递归与迭代】（Python） LeetCode算法题|深度优先遍历

给定一个二叉树，返回它的后序遍历。

文章图片

进阶: 递归算法很简单，你可以通过迭代算法完成吗？
解法一：递归

# Definition for a binary tree node. # class TreeNode: #def __init__(self, x): #self.val = x #self.left = None #self.right = Noneclass Solution: def __init__(self): self.ans = [] def postorderTraversal(self, root: TreeNode) -> List[int]: if not root: return self.ans self.postorderTraversal(root.left) self.postorderTraversal(root.right) self.ans.append(root.val) return self.ans

【LeetCode算法题|LeetCode —— 145. 二叉树的后序遍历【递归与迭代】（Python）】解法二：迭代

class Solution(object): def postorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ if root is None: return []stack = [root, ]# 栈，后进先出 output = []# 存储输出 while stack: root = stack.pop() output.append(root.val) if root.left is not None: stack.append(root.left) if root.right is not None: stack.append(root.right)return output[::-1]# 逆序输出